《剑指Offer》-01数组

发表于 | 分类于

二维数组中的查找

题目描述 【简单】
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function Find(target, array)
{
    // write code here
    const col=array.length,
       row=array[0].length;
    //从矩阵左下角找起
    let c=col-1,
        r= 0 ;
 
    while(c>=0 && r<=row-1){
        if(array[c][r]<target){
            r++;
        }else if(array[c][r]>target){
            c--;
        }else{
            return true;
        }
    }
    return false;
}

总结：根据数组的规律，可从数组的左下或右上角找起，根据大小的方向性，依次排除掉列或者行。或者暴力法解题。

数组中重复的数字

题目描述【简单】
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function duplicate(numbers, duplication)
{
    // write code here
    //这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    //函数返回True/False
    for(var i=0;i<numbers.length;i++){
        for(var j=i+1;j<numbers.length;j++){
            if(numbers[i]===numbers[j]){
                duplication[0]=numbers[i];
                return true;
            }
        }
    }
    return false;
}

总结：遍历数组，比较无脑

构建乘积数组

题目描述
给定一个数组A[0,1,…,n-1],请构建一个数组B[0,1,…,n-1],其中B中的元素B[i]=A[0] *A[1]*…*A[i-1]*A[i+1]*…*A[n-1]。不能使用除法。（注意：规定B[0] = A[1] * A[2] * … * A[n-1]，B[n-1] = A[0] * A[1] * … * A[n-2];）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function multiply(array)
{
    // write code here
    let n=array.length,
        B=[];
    for(let i=0;i<n;i++){
        B[i]=1;
        for(let j=i+1;j<n;j++){
            B[i]=B[i]*array[j];
        };
        for(let k=i-1;k>=0;k--){
            B[i]=B[i]*array[k];
        }
    }
    return B;
}

总结：将数组分成上三角跟下三角，依次相乘

0%