剑指offer学习笔记：8.1 数组

面试题51：数组中重复的数字

在一个长度为n的数组中，所有数字都在0到n-1的范围内。数组中的某些数字是重复的，但是不知道有几个数字重复了，也不知道每个数字重复了几次，找到数组中任意一个重复数字。
leetcode链接 https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/

class Solution {
public:
   int findRepeatNumber(vector<int>& nums) {
       if (nums.size() == 0)
       {
           return 0;
       }
       for(int i = 0; i < nums.size(); i++)
       {
           // cout << i << endl;
           // cout << nums[i] << endl;
           while (nums[i] != i)
           {
               if (nums[i] < i)
               {
                   return nums[i];
               }
               if (nums[nums[i]] == nums[i])
               {
                   return nums[i];
               }
               int tmp = nums[i];
               nums[i] = nums[nums[i]];
               nums[tmp] = tmp;    // 注意是nums[tmp]
           }
       }
       return -1;
   }
};

解题思路：
思路1：排序，相邻元素判断
思路2：遍历，建hash表
思路3：如果没有重复的数，则建立n位数组，刚好每一位下标都可以放与之对应的一位元素。因行数组与其对应下标重排操作。以数组{1,3,2,0,2,5,3}进行分析。首先看下标0位置元素1，与下标不符，交换下标0位置元素与下标1位置元素，得到数组{3,1,2,0,2,5,3}。判断当前下标0对应元素3，仍与下标不符，交换0位元素与下标为3元素，得到数组{0,1,2,3,2,5,3}。当前0位元素与下标相符，像后进行判断。循环到第4位发现，第四位元素为2，但是因为2刚才已经判断过了，已经有一个元素2了，因此找到第一个重复元素，为2。

面试题52：构建乘积数组

给定一个数组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]，不能使用除法。
leetcode链接 https://leetcode-cn.com/problems/gou-jian-cheng-ji-shu-zu-lcof/

class Solution {
public:
   vector<int> constructArr(vector<int>& a) {
       vector<int> left, right;
       left.push_back(1);
       right.push_back(1);
       for(int i = 1; i < a.size(); i++)
       {
           left.push_back(left[i-1]*a[i-1]);
           right.push_back(right[i-1] * a[a.size() - i]);
       }
       vector<int> result;
       for(int i = 0; i < a.size(); i++)
       {
           // cout << "left: " << left[i] << " right: " << right[a.size() - 1 - i];
           result.push_back(left[i] * right[a.size() - 1 - i]);
       }
       return result;
   }
};

解题思路：
参考链接 https://leetcode-cn.com/problems/gou-jian-cheng-ji-shu-zu-lcof/solution/mian-shi-ti-66-gou-jian-cheng-ji-shu-zu-biao-ge-fe/
首先，从暴力思路出发，不能用除法，暴力思路就只能是每次循环的时候，循环0 - i-1和i+1 - n，复杂度是n2。但是将乘法分为两部分来看，前一部分f(n) = (0 - i-1)乘积，g(n) = (i+1 - n-1)乘积，可得到关系f(n) = f(n-1) *（下标i） g(n-1) = g(n) *（下标i）,所谓矩阵法中的矩阵就是为了让大家更加清晰的看明白这个逻辑关系。直观写法，两轮循环，两个中间数组

class Solution {
public:
    vector<int> constructArr(vector<int>& a) {
        vector<int> left, right;
        left.push_back(1);
        right.push_back(1);
        for(int i = 1; i < a.size(); i++)
        {
            left.push_back(left[i-1]*a[i-1]);
        }
        for(int j = 1; j < a.size(); j++)
        {
            right.push_back(right[j-1] * a[a.size() - j]);
        }
        vector<int> result;
        for(int i = 0; i < a.size(); i++)
        {
            // cout << "left: " << left[i] << " right: " << right[a.size() - 1 - i];
            result.push_back(left[i] * right[a.size() - 1 - i]);
        }
        return result;
    }
};