刷题-数组专项

数组

1. 二维数组中的查找
   题目描述：在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
   笔记： 这个题之间就做过，所以思路是没有问题的。提交了几次一直运行超时，最后在查找到目标后提前返回以降低循环次数，成功通过。
   代码：

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        if(array.size() == 0)
            return false;
        if(array[0].size() == 0)
            return false;
        int size = array[0].size();
        int xIndex = 0, yIndex = size - 1;
        bool res = false;
        while(xIndex < size && yIndex >= 0)
        {
            if(target < array[xIndex][yIndex])
                yIndex--;
            else if(target > array[xIndex][yIndex])
                xIndex++;
            else
            {
                res = true;
                return res;
            }
        }
        return res;
    }
};

运行耗时：10ms
占用内存：1504k

2. 数组中重复的数字
   题目描述：在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
   笔记：没啥好的思路，直接暴力求解试试，发现也可以通过

bool duplicate(int numbers[], int length, int* duplication) {
        for(int i = 0; i < length; i ++)
        {
            for(int j = i + 1; j < length; j ++)
            {
                 if(numbers[i] == numbers[j])
                 {
                     *duplication = numbers[i];
                     return true;
                 }
            }
        }
        return false;
    }

3. 构建乘积数组
   题目描述：给定一个数组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];）
   笔记：这个题的重点在于不让用除法，那么就只能相乘了。相乘时需要去除当前索引的元素号，用取余操作比较合适。
   代码

class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        vector<int> res(A.size(), 1);
        int size = A.size();
        if(size == 1)
            res[0] = A[0];
        // n:1  B[0]<0>
        // n:2  B[0]<1>, B[1]<0>
        // n:3  B[0]<1,2>, B[1]<0,2>, B[2]<0,1>
        // n:4  B[0]<1,2,3>, B[1]<0,2,3>, B[2]<0,1,3>, B[3]<0,1,2>
        // n:5  B[0]<1,2,3,4>, B[1]<0,2,3,4>, B[2]<0,1,3,4>, B[3]<0,1,2,4>, B[4]<0,1,2,3>
        for(int i = 0; i < size; i++)
        {
            for(int j = 1; j < size; j++)
            {
                res[i] *= A[(j + i + size)%size];
            }
        }
        return res;
    }
};

运行耗时：3ms
占用内存：476k