这个题目名字有点怪，需要注意“所有”修饰最后的“数字”，而不是“数组”。

题目描述

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

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

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

示例:

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

输出:
[5,6]

解法思路

解法一

将元素值作为下标，按照这个下标去对应的位置加负号。
最后没有被加负号的元素，其下标即“消失的数字”。

解法二

同解法一，只是将加负号变为加数组长度。
最后小于数据长度的元素，其下标即“消失的数字”。

解法三

将元素值作为下标，将该元素移动到下标的位置，除非该位置的元素和自己相等。
最后没有在自己位置的元素，其下标即为“消失”的数字。

示例：4，3，2，7，8，2，3，1

• 第1个元素是

  • 4，和nums[3]=7交换：7，3，2，4，8，2，3，1
  • 7，和nums[6]=3交换：3，3，2，4，8，2，7，1
  • 3，和nums[2]=2交换：2，3，3，4，8，2，7，1
  • 2，和nums[1]=3交换：3，2，3，4，8，2，7，1
  • 3，无需和nums[2]=3交换

• 第2个元素是

  • 2，当前位置即nums[1]，无需交换

• 第3个元素是

  • 3，和nums[2]=3无需交换

• 第4个元素是

  • 4，和nums[3]=4无需交换

• 第5个元素是

  • 8，和nums[7]=1交换：3，2，3，4，1，2，7，8
  • 1，和nums[0]=3交换：1，2，4，3，3，2，7，8
  • 3，和nums[2]=4交换：1，2，3，3，4，2，7，8
  • 4，和nums[3]=3交换：1，2，3，4，3，2，7，8
  • 3，和nums[2]=3无需交换

• 第6个元素是
  -2，和nums[1]=2无需交换

  • 第7个元素和第8个元素也无需交换

结果：1，2，3，4，3，2，7，8

nums[4]!=4+1
nums[5]!=5+1

所以5和6是消失的数字。

代码示例

vector<int> findDisappearedNumbers(vector<int>& nums) { // 解法一
    vector<int> res;

    for (int i = 0; i < nums.size(); ++i) {
        int index = abs(nums[i]) - 1;
        nums[index] = -abs(nums[index]);
    }

    for (int i = 0; i < nums.size(); ++i) {
        if (nums[i] > 0)
            res.push_back(i+1);
    }

    return res;
}

vector<int> findDisappearedNumbers2(vector<int>& nums) { // 解法二
    vector<int> res;

    for (int i = 0; i < nums.size(); ++i) {
        int index = (nums[i] - 1) % nums.size();
        nums[index] += nums.size();
    }

    for (int i = 0; i < nums.size(); ++i) {
        if (nums[i] <= nums.size())
            res.push_back(i + 1);
    }

    return res;
}

void swap(vector<int>& nums, int index1, int index2) {
    if (index1 == index2)
        return;

    nums[index1] = nums[index1] ^ nums[index2];
    nums[index2] = nums[index1] ^ nums[index2];
    nums[index1] = nums[index1] ^ nums[index2];
}

vector<int> findDisappearedNumbers3(vector<int>& nums) { // 解法三
    vector<int> res;

    for (int i = 0; i < nums.size(); ++i) {
        while (nums[i] != nums[nums[i] - 1])
            swap(nums, i, nums[i] - 1);
    }

    for (int i = 0; i < nums.size(); ++i)
        if (nums[i] != i + 1)
            res.push_back(i + 1);

    return res;
}