[剑指offer] 数组

二维数组中的查找

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

解题思路：
从 右上角 往左下角遍历， 时间复杂度 O(col+row).

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        //row 
        int i = 0;
        // column
        int j = array[0].size()-1;
        // NE  从右上角 往左下角遍历
        while( i <= array.size()-1 && j>=0){
            if(array[i][j] > target){
                j--;
            }else if(array[i][j] < target){
                i++;
            }else{
                return true;
            }
        }
        return false;
    }
};

数组中重复的数字

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

解题思路：
这题有复杂度要求 O(N) + O(1), 所以 基于排序 和 散列 的 去重不适用。

我们观察这题的条件， 长度为n的数组里的所有数字都在0到n-1的范围内，那么我们通过 两两替换， 可以把 值 为 i 的数字 调整到 index 为 i 的位置上。
两两替换的过程中

• 要么 替换到 与 index 相等的值， 那么我们把 cur ++
• 要么 遇到重复。

class Solution {
public:
    // Parameters:
    //        numbers:     an array of integers
    //        length:      the length of array numbers
    //        duplication: (Output) the duplicated number in the array number
    // Return value:       true if the input is valid, and there are some duplications in the array number
    //                     otherwise false
    bool duplicate(int numbers[], int length, int* duplication) {
        //O(N) + O(1)
        
        int cur = 0;
        while(cur < length){
            //当前 值 和 index 之否一致
            //不一致 ： 需要swap
            if(numbers[cur] != cur){
                while(numbers[cur]!= cur){
                    if(numbers[cur] == numbers[numbers[cur]]){
                        duplication[0] = numbers[numbers[cur]];
                        return true;
                    } 
                    swap(numbers[cur],numbers[numbers[cur]]);
                }
                cur++;
            // 一致
            }else{
                cur++;
            }
        }
        
        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[i] = A[0]....A[i-1] A[i+1]...A[n-1]
分解成 C[i] = A[0]....A[i-1]
D[i] = A[n-1].....A[i+1]
B[i] = C[i]×D[i]

class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        // B[i] = A[0]....A[i-1]  A[i+1]...A[n-1]
        vector<int> B(A.size(),1);
        
         //first, calculate  A[0]....A[i-1]
        //1 ,A[0] ,A[0]*A[1]
        for(int i = 0, product = 1; i < A.size(); product*=A[i] ,i++){
            B[i] = product;
        }
        // then A[i+1]...A[n-1]
       //1, A[n-1], A[n-1]A[n-2]

        for(int i = A.size()-1,product = 1; i >= 0; product*=A[i], i--){
            B[i]*=product;
        }
        return B;
    
    }
};