[leetcode每日一题2021/2/13]448. 找到所有数组中消失的数字

题目来源于leetcode，解法和思路仅代表个人观点。传送门。
难度：简单
时间：-

题目

给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。

找到所有在 [1, n] 范围之间没有出现在数组中的数字。

您能在 不使用额外空间且时间复杂度为O(n) 的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。

示例:

输入:
[4,3,2,7,8,2,3,1]

输出:
[5,6]

思路

不使用额外空间且时间复杂度为O(n)，即进行一次遍历+使用指针（或原地修改数组）

原地哈希

思路来源于之前做过的一道题41. 缺失的第一个正数

咋一看，题目非常类似，所以稍微想了一想，尝试使用原地哈希的方法

---

维护一个映射关系：将n映射到数组的n-1的位置上

之后再进行一次遍历，如果当前位置的元素不满足映射关系，当前位置的元素就为缺失。

代码

class Solution {
    
public:
    template <typename T>
    void swap(T &a,T &b){
    
        T temp;
        temp = a;
        a = b;
        b = temp;
    }
    vector<int> findDisappearedNumbers(vector<int>& nums) {
    
        vector<int> ans;
        //数组长度
        int n = nums.size();
        //映射条件：n映射到 数组n-1的位置
        for(int p=0;p<n;p++){
    
            //n-1位置上的数，不为n，交换二者
            /* * 1. 为什么使用while？ * 交换后，当前位置的元素可能又不满足映射条件，所以还需要继续交换 * 2. 结束之后的状态？ * （1）当前位置的元素，恰好满足映射条件。 * 如：1 3 2 => 1 2 3（指针p为1，交换3-2之后，满足映射关系） * （2）当前位置的元素，不满足映射条件。但对应位置的元素已经满足映射关系了。 * 如：1 3 3 => 1 3 3 （指针p为1，nums[3-1]恰好==3，不需要交换） */
            while(nums[nums[p]-1] != nums[p]){
    
                swap(nums[p],nums[nums[p]-1]);
            }
        }
        //再进行一个遍历
        for(int p=0;p<n;p++){
    
            //如果当前位置的元素不满足映射关系，加入答案
            if(nums[p] != p+1){
    
                ans.push_back(p+1);
            }
        }
        return ans;
    }
};

算法复杂度

时间复杂度： O(n)，最坏O(2n)。while循环在第一个元素的时候，先把所有元素都映射好了
空间复杂度： O(1)，答案不计算在空间复杂度中，使用原数组原地修改的策略。