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
