【LeetCode】448. Find All Numbers Disappeared in an Arrayを解く

問題へのリンク

問題概要

$1 \leq a[i] \leq n$ ($n$は配列のサイズ)となるような整数からなる配列が与えられる．
この配列には，２回現れる要素と１回現れる要素から構成されている．

この時，$[1,n]$の整数のうち配列に現れない全ての要素を答える．

例：

Input:
[4,3,2,7,8,2,3,1]

Output:
[5,6]

制約

• 戻り値以外の空間を確保せずに$O(n)$の時間計算量で実装する

考えたこと

戻り値以外に空間を確保する場合は，$n$次元配列$count = [True,True, ..., True]$を用意して，$nums$に出現した整数$num$をインデクスとして

count[num-1] = False

のようにすれば，$count[i] == True$となるインデクスからなる配列が所望の出力となる．

この考えに基づいたコードは以下のとおりである：

class Solution(object):
    def findDisappearedNumbers(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        
        count = [True]*len(nums)
        
        for n in nums:
            count[n-1] = False
            
        return [i+1 for i, c in enumerate(count) if c == True]

但し，この回答では戻り値以外に配列$count$を利用しているため制約を満たしていない．

従って，既存のデータ（ここでは入力の配列$nums$）を用いて$count$と同様の役割を果たすことを考える必要がある．

問題から，$1 \leq a[i] \leq n$なので各要素の正/負にTrue/Falseの役割を果たせば追加の空間を確保せずに実装できそうだ：

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 list(i+1 for i,num in enumerate(nums) if num > 0)