[LeetCode][Python]448. 找到所有數(shù)組中消失的數(shù)字

給定一個(gè)范圍在 1 ≤ a[i] ≤ n ( n = 數(shù)組大小 ) 的 整型數(shù)組，數(shù)組中的元素一些出現(xiàn)了兩次，另一些只出現(xiàn)一次。

找到所有在 [1, n] 范圍之間沒有出現(xiàn)在數(shù)組中的數(shù)字。

您能在不使用額外空間且時(shí)間復(fù)雜度為O(n)的情況下完成這個(gè)任務(wù)嗎? 你可以假定返回的數(shù)組不算在額外空間內(nèi)。

示例:

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

輸出:
[5,6]

思路：

1. 根據(jù)Python set不允許出重復(fù)元素，可以使用set造一個(gè)全部元素的，減去目標(biāo)的set，剩下的就是沒有出現(xiàn)的。不過，可能不能滿足不使用額外空間這個(gè)要求

2. 利用索引把數(shù)組自身當(dāng)作哈希表處理，將所有正數(shù)作為數(shù)組下標(biāo)，置對(duì)應(yīng)數(shù)組值為負(fù)值。那么，仍為正數(shù)的位置即為（未出現(xiàn)過）消失的數(shù)字。

這個(gè)思路很巧妙，以至于看了好幾遍也沒明白。如果該正數(shù)存在數(shù)組里面，數(shù)組對(duì)應(yīng)的元素就會(huì)被置為負(fù)值，如果仍為正值，說明該正數(shù)就不存在數(shù)組里面

若將題目要求改為數(shù)組中每個(gè)元素出現(xiàn)的可能次數(shù)是 n 次,求出數(shù)組中出現(xiàn)此次為偶數(shù)（奇數(shù)）次的元素（出現(xiàn) 0 次也算偶數(shù)次）。
則代碼需要更改為

    for num in nums:
        index = abs(num) - 1
        # 保持nums[index]為相反數(shù),唯一和上面的解法不同點(diǎn)就是這里，好好體會(huì)
        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))