腦筋急轉彎 找出消失的數字 與 重複的數字 Set Mismatch_Leetcode #645
題目敘述
題目會給定一個整數陣列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:
