[LeetCode][Python]448. 找到所有數(shù)組中消失的數(shù)字
給定一個范圍在 1 ≤ a[i] ≤ n ( n = 數(shù)組大小 ) 的 整型數(shù)組，數(shù)組中的元素一些出現(xiàn)了兩次，另一些只出現(xiàn)一次。
找到所有在 [1, n] 范圍之間沒有出現(xiàn)在數(shù)組中的數(shù)字。
您能在不使用額外空間且時間復雜度為O(n)的情況下完成這個任務嗎? 你可以假定返回的數(shù)組不算在額外空間內(nèi)民晒。
示例:
輸入:
[4,3,2,7,8,2,3,1]
輸出:
[5,6]
思路：
根據(jù)Python set不允許出重復元素蘸嘶，可以使用set造一個全部元素的炬灭，減去目標的set指煎，剩下的就是沒有出現(xiàn)的粗蔚。不過尝偎，可能不能滿足不使用額外空間這個要求
利用索引把數(shù)組自身當作哈希表處理，將所有正數(shù)作為數(shù)組下標鹏控，置對應數(shù)組值為負值致扯。那么，仍為正數(shù)的位置即為（未出現(xiàn)過）消失的數(shù)字当辐。
這個思路很巧妙抖僵，以至于看了好幾遍也沒明白。如果該正數(shù)存在數(shù)組里面缘揪，數(shù)組對應的元素就會被置為負值耍群，如果仍為正值，說明該正數(shù)就不存在數(shù)組里面
若將題目要求改為數(shù)組中每個元素出現(xiàn)的可能次數(shù)是 n 次,求出數(shù)組中出現(xiàn)此次為偶數(shù)（奇數(shù)）次的元素（出現(xiàn) 0 次也算偶數(shù)次）寺晌。
則代碼需要更改為
for num in nums:
index = abs(num) - 1
# 保持nums[index]為相反數(shù),唯一和上面的解法不同點就是這里世吨，好好體會
nums[index] = -nums[index]
#偶數(shù)次
return [i + 1 for i, num in enumerate(nums) if num > 0]
#奇數(shù)次
return [i + 1 for i, num in enumerate(nums) if num < 0]
#!/usr/bin/env python
class Solution(object):
def findDisappearedNumbers(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
for num in nums:
index = abs(num) - 1
nums[index] = -abs(nums[index])
return [i + 1 for i, num in enumerate(nums) if num > 0]
if __name__ == '__main__':
sol = Solution()
alist = [4,3,2,7,8,2,3,1]
print(sol.findDisappearedNumbers(alist))
