腦筋急轉彎 找出消失的數字 與 重複的數字 Set Mismatch_Leetcode #645

Sigmund null on Unsplash

題目敘述

題目會給定一個整數陣列nums，原本裡面包含有整數1到n，但是中間不小心出了差錯，導致有一個數字消失了，而另一個數字重複了。

請找出重複的數字以及消失的數字，並且

以陣列的形式[重複的數字, 消失的數字]返回這兩個數字。

例如:

[1,3,3,4]

消失的數字是2，重複的數字是3

答案返回[3, 2]

題目的原文敘述

測試範例

Example 1:

Input: nums = [1,2,2,4]
Output: [2,3]

Example 2:

Input: nums = [1,1]
Output: [1,2]

約束條件

Constraints:

• 2 <= nums.length <= 10^4

輸入陣列的長度介於2~10^4 之間。題目保證陣列長度至少為2。

• 1 <= nums[i] <= 10^4

每個陣列元素值介於1 ~ 10^4 之間。

演算法

除了第一直覺的字典統計出現次數的演算法之外。

還有一個偏向數學推理的演算法。

題目說 有一個數字消失，有一個數字重複。

所以，

理想中(沒有出錯)的總和 perfect sum = 1 + 2 + ... + n

= 數列和公式 = 1 * (n+1) / 2

第一步:

perfect sum - 輸入陣列中曾經出現過的數字(相當與建立集合set的動作)總和

= 消失的數字

到這一步，就已經找到消失的數字。

第二步:

接下來，

理想中(沒有出錯)的總和 perfect sum + 重複的數字

= 1 + 2 + ... + n + 重複的數字

= { 1 * (n+1) / 2 } + 重複的數字

= (有出錯的)輸入陣列的總和 + 消失的數字

剛剛第一步已經知道消失的數字，而pefect sum透過數列和公式可以直接求出，輸入陣列的總和也只要直接相加就可以知道。

現在未知項是重複的數字，這邊只要做個簡單的加減法計算就可以得到重複的數字。

最後，以陣列的形式[重複的數字, 消失的數字]返回答案即可。

程式碼

class Solution:
    def findErrorNums(self, nums: List[int]) -> List[int]:
        
        # get the size of input array, nums
		
        n = len(nums)
        
        # perfect_sum 
        # = n * ( n+1 ) // 2
        # = sum of unique element + missing element
		
        perfect_sum = n * (n+1) // 2

        # compute the missing element from summation formula
		
        missing_element = perfect_sum - sum( set(nums) )

        # perfect sum + repeated element = sum of nums + missing element
        # compute the repeated element 
		
        repeated_element = sum(nums) + missing_element - perfect_sum

        return [ repeated_element, missing_element]

複雜度分析

時間複雜度:

從頭到尾掃描過每個元素，建立集合 和 計算數列和，所需時間為O(n)。

空間複雜度:

建立集合set(nums)，所需空間為O(n)

關鍵知識點

從數字應該出現一次的標準答案 1 + 2 + 3 + ... + n

聯想到可以用數列和的公式求出，並且推理出消失的數字和重複的數字是誰。

Reference:

[1] Set Mismatch - LeetCode