LeetCode #448 找到所有数组中消失的数字-526互联

基本思路

　　为了满足题目要求的不使用额外的存储空间（当然返回的数组除外），并且时间复杂度控制在O（n），最多只能常数级别遍历，因此考虑将原数组视作一个"哈希表"。

　　遍历原数组，将【1，n】上的值域映射到【0，n-】的坐标上，某个数x扫描到一次则将这个数x映射的 x-1的坐标处的值加上n。

　　然后再次遍历原数组，如果某个元素num【i】不超过n则说明这个数对应的映射未被扫描过，i+1则代表缺失的数，可以加入作为结果返回的vector数组中。

标程

 1 class Solution {
 2 public:
 3     vector<int> findDisappearedNumbers(vector<int>& nums) {
 4         int n = nums.size();
 5         for(auto& num : nums){
 6             int x = (num - 1) % n;
 7             nums[x] += n;
 8         }
 9         vector<int>res;
10         for(int i = 0; i < n; i++){
11             if(nums[i] <= n){
12                 res.push_back(i+1);
13             }
14         }
15         return res;
16     }
17 };

时间复杂度

　　O（N）