数组

1.递归求和：

function sum(arr,n){
    return n==0?  0 : sum(arr,n-1)+arr[n-1];
}
var arr=[1,2,3];
var n=arr.length;
sum(arr,n);

2.for循环打印二维数组：

function printErarr(arr) {
    var row=arr.length;
    var col=arr[0].length;
    var printarr=[];
    for(var i=0;i<row;i++){
        for(var j=0;j<col;j++){
            printarr.push(arr[i][j]);
        }
    }
    return printarr;
}
var arr=[[1,2,3,4],[5,6,7,5],[2,4,56,8]];
printErarr(arr);

3.用递归判断数组是否递增：

结束条件：数组长度为1，返回true;
递归条件：如果最后一个大于倒数第二个，则再对倒数第二个与倒数第三个进行比较。

function isIncrese(arr,n) {
    if(n==1){return true;}
    return (arr[n-1]>=arr[n-2]) && isIncrese(arr,n-1);
}

var arr=[1,2,3,4];
var n=arr.length;
isIncrese(arr,n);

4.如何实现二分查找（数组有序，单调递增）：（二分查找只对有序数据集有效）

1.将数组的第一个位置设置为start；
2.将数组的最后的位置设置为end；
3.只要end>=start，就进行循环：
mid值为end与start的中间值，判断arr[mid]与findData的大小：
如果<,则start为mid+1;
如果>，则end为mid-1;
如果=,则返回mid值即可。

   function binarySearch(arr,findData) {
        var n=arr.length;
        var start=0,end=n-1;
        while(end>=start){
           var mid=parseInt(start+(end-start)/2);
           if(arr[mid]<findData){
               start=mid+1;
           }
           else if(arr[mid]>findData){
               end=mid-1;
           }
           if(arr[mid]==findData){
               return mid;
           }
        }
        return -1;
    }
    var arr=[1,4,7,9,10];
    var findData=9;
    binarySearch(arr,findData);

5.如何在排序数组中，找出给定数字出现的次数：

在上述的二分查找中的找到的if语句中，将end,start均设为mid，
加入两个循环：
向后循环，如果后面的数等于mid中的值，则将right+1;
向前循环，如果前面的数等于mid中的值，则将left+1;
最后返回end-start+1;

    function binaryNum(arr,dataNum) {
        var n=arr.length;
        var start=0,end=n-1;
        while(end>=start){
           var mid=parseInt(start+(end-start)/2);
           if(arr[mid]<dataNum){
               start=mid+1;
           }
           else if(arr[mid]>dataNum){
               end=mid-1;
           }
           if(arr[mid]==dataNum){
               var rightmid=mid+1;
               var leftmid=mid-1;
               end=mid;
               start=mid;
               while(arr[rightmid] && arr[rightmid]==dataNum){
                    end=mid+1;
                    rightmid+=1;
                }
               while(arr[leftmid] && arr[leftmid]==dataNum){
                    start=mid-1;
                    leftmid-=1;
                }
                return end-start+1;
           }
        }
        return -1;
    }
    var arr=[1,4,5,7,9,9,9,10];
    var dataNum=9;
    binaryNum(arr,dataNum);

6.如何计算两个有序（递增）整型数组的交集：

两个循环对两个数组进行嵌套循环。
如果>，则将arr2指针向后；
如果=，则判断是否是第一次出现此数值，如果是，就将其加入新数组中，并跳出内部循环。如果不是，就跳出内部循环；
如果<，则跳出内部循环。

function mixed(arr1,arr2) {
    var n1=arr1.length;
    var n2=arr2.length;
    var findarr=[];
    for(var i=0;i<n1;i++){
        for(var j=0;j<n2;j++){
            if(arr1[i]>arr2[j]){
                continue;
            }
            if(arr1[i]==arr2[j]){
                if(arr1[i-1] && arr1[i]!=arr1[i-1]) {
                    findarr.push(arr1[i]);
                }
                break;
            }
            else {
                break;
            }
        }
    }
    return findarr
}
var arr1=[1,2,3,3,4,5];
var arr2=[3,4,5,6,7,8,9];
mixed(arr1,arr2);

7.如何找出数组中重复次数最多的数？

使用对象，key中存放值，value中存放次数。

   function GetMaxNum(arr) {
        var o={};
        var len=arr.length;
        var max=0;
        for(var i=0;i<len;i++){
            var name=arr[i];
            if(o[name]){
                o[name]+=1;
            }
            else{
                o[name]=1;
            }
        }
        for(var key in o){       //注意对对象的遍历的写法
            if(o[key]>max){
                max=o[key];
                console.log("次数最多为"+max+"次");
            }
        }
        for(var key in o){
            if(o[key]==max){
                console.log("值为："+key)
            }
        }
    }
    var arr=[1,1,1,2,2,3,4,4,4,7,7];
    GetMaxNum(arr);

8.如何在O(n)的事件复杂度内找出数组中出现次数超过了一半的数：

哈希法：如7中所示，创建一个hash_map，返回最大value的key值。

function findMost(arr) {
    var n=arr.length;
    var o={};
    var max=0;
    var num;
    for(var i=0;i<n;i++){
        var name=arr[i];
        if(o[name]){
            o[name]+=1;
        }
        else{
            o[name]=1;
        }
    }
    for(var key in o){
        if(o[key]>max){
           max=o[key];
           num=parseInt(key);
        }
    }
    return num;
}
var arr=[1,2,2,2,2,3];
findMost(arr);