16-找到所有数组中消失的数字

自己的做法

算法思想

因为数组满足 $$1$$ <= $a_i$ <= n，所以可以以数组下标来作为对应数字。

返回数组为result，首先根据输入数组nums的长度length，在result中插入length个0。

然后遍历数组nums，对于每个数字，将该数字 - 1，并作为result的下标，对应元素 + 1。

遍历结束后，没有出现的数字，作为result的索引，对应数字会是0。

就找到了所有消失的数字。

然后根据 移动零 那道题的算法，稍微改一下，将所有0对应的索引挪到数组最前面来。然后删除其他元素即可。

算法实现

class Solution {
public:
    static vector<int> findDisappearedNumbers(vector<int>& nums) {
        vector<int> result;
        int length = nums.size();

        for(int i = 0; i < length; i++) {
            result.push_back(0);
        }
        for(int i = 0; i < length; i++) {
            result[nums[i] - 1]++;
        }

        int left = 0, right = 0, count = 0;
        while (right < length) {
            if(result[right] == 0) {
                result[left] = right + 1;
                count++;
                left++;
            }
            right++;
        }
        for(int i = 0; i < length - count; i++) {
            result.pop_back();
        }

        return result;

    }
};

性能分析

时间复杂度：$O(n)$。

空间复杂度：以为使用返回数组就不算额外空间。但是要添加n个元素。其实还是用了$O(n)$。

并不是在返回数组操作就不算额外空间。

官方做法

算法思想

可以把输入数组本身作为一个哈希表。

遍历数组，对于数组每一个元素x，令num[x - 1] += length，其中length是数组长度。

因为1 <= $a_i$ <= n，所以遍历完成后，消失的数字作为下标，对应元素一定满足该关系。而出现的数字作为下标，对应元素一定大于n。

注意：因为访问到的元素有可能增加过，因此要取模来获得下标。

算法实现

class Solution {
public:
    static vector<int> findDisappearedNumbers(vector<int>& nums) {
        vector<int> result;
        int length = nums.size();
        for(int i = 0; i < length; i++) {
            int x = (nums[i] - 1) % length;
            nums[x] += length;
        }
        for(int i = 0; i < length; i++) {
            if(nums[i] <= length) {
                result.push_back(i + 1);
            }
        }
        return result;

    }
};

性能分析

时间复杂度：$O(n)$

空间复杂度：$O(1)$