448. 找到所有数组中消失的数字

1. 题目

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

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

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

示例:

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

输出:
[5,6]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 思路分析

如果可以使用额外空间，那么这个题就简单许多。直接用使用哈希表法来做。但重点在于不能使用额外空间，那么我们只能换一个思路。

在正式分析前，我要感谢LeetCode的评论区。这个思路是来自于评论区。

既然整型数组的最大最小范围是给定的，那么这一点应该可以被利用。以题目中的数组为例，说明一下此思路：

假设数组长度为L，题目中数组数字范围是[1, L]；
如果该数字i在数组中出现，则将第i - 1位变为其相反数，因为编程语言中是从0开始计位的；
经过步骤2走一趟后，只需再遍历一遍改造过的数组。如果第i位为正，则将i + 1（实际位置）添加到要返回的列表中即可。

总结：上面思路最精妙的地方在于使用了题目中的特性。

3. 题解

哈希表法(Python，非常容易理解)

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        L = len(nums)
        if L == 0:
            return None

        # Initialise a list used to return.
        res = list()

        # Initialise a hashmap named "comp".
        comp = dict()
        for i in range(1, L + 1):
            comp[i] = 0

        # Sort the array "nums".
        nums.sort()

        # Use dict to record the times every number appearing.
        for j in range(L):
            comp[nums[j]] += 1      
        
        # If the value of key "k" is 0, then "k" will be appended into the list "res".
        for k in comp:
            if comp[k] == 0:
                res.append(k)
        
        return res

但哈希表法使用了额外空间，不符合我们的思路。可以看，在LeetCode中跑分也很低：

hash448.png

上面讲述的思路(Java实现)

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        int L = nums.length;
        // 进入正题
        List<Integer> res = new ArrayList<Integer>();
        for(int i = 0; i < L; ++i){
            nums[Math.abs(nums[i]) - 1] = -Math.abs(nums[Math.abs(nums[i]) - 1]);
        }
        for(int h = 0; h < L; ++h){
            if(nums[h] > 0){ res.add(h + 1); }
        }
        return res;
    }
}

Java的跑分：

448java.png

用Python实现如下（附跑分）：

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        L = len(nums)
        res = list()
        for i in range(L):
            nums[abs(nums[i]) - 1] = -abs(nums[abs(nums[i]) - 1]) 
        for _ in range(L):
            if nums[_] > 0:
                res.append(_ + 1)
        return res

从下图跑分中可看出，新思路相比用哈希表，性能上改进诸多：

448new.png