一魚多吃 用XOR性質來解 失蹤的數字Missing Number Leetcode #268

更新於 發佈於 閱讀時間約 5 分鐘
raw-image

這題題目在這裡:

題目會給定一個陣列,長度為n,裡面的數字都是獨一無二,落在0~n的範圍。

要求我們找出那個不見的數字 Missing Number

註:
(n+1)個數字,無法同時放入n個不同的格子,必定有一個數字不見了。


測試範例:

Example 1:

Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.

Example 2:

Input: nums = [0,1]
Output: 2
Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.

Example 3:

Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.

約束條件:

Constraints:

  • n == nums.length
  • 1 <= n <= 104
  • 0 <= nums[i] <= n
  • All the numbers of nums are unique.

Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?


演算法:

除了傳統的集合檢查法之外,我們還可以用化簡的技巧,把這題映射到另一個問題Single Number,就可以用XOR Self-inverse的特性來找出Missing Number。


我們把 array index 一起加進來考慮,可以得到如下的示意圖

raw-image

再次回顧這個重要的性質(類似鴿籠原理的衍伸):

0~n 總共(n+1)個數字,無法同時放入n個不同的格子,必定有一個數字不見了。


令 missing_finder 初始值為 n = 陣列長度

接著對index滾動計算XOR,再對陣列本身裡面的數字滾動計算XOR,最後留下來的數字,就是我們的所求 Missing Number。

為什麼? 因為,扣掉 Missing Number之外的數字,其他數字都會成雙成對出現兩次一次是在index一次是在陣列本身裡面的數字 或者 missing_finder 的初始值

例如:

array = [0, 1, 3]

index = [0, 1, 2]

Result 初始值 = n = 陣列長度 = 3

所有數字,除了missing number 2 之外,其他數字0, 1, 3都會成雙成對出現兩次。


程式碼:

class Solution:
 def missingNumber(self, nums: List[int]) -> int:
  
  size = len(nums)
  
  missing_finder = size
  
  for index, number in enumerate(nums):
   
   # all existed number must exist twice, one in index, the other in number
   # only the missing one exist once, so it will remained in missing finder naturally due to XOR property
   missing_finder ^= ( index )
   missing_finder ^= ( number )
   
  return missing_finder

時間複雜度:

O( n ) 只需要一次線性掃描。

空間複雜度:

O( 1 ) 只需要臨時變數去儲存XOR 滾動計算的結果。


學完這題之後,記得吸收沉澱一下,
回去複習 Single NumberFind the difference 這兩題喔,背後用到的都是同樣的觀念,也都用到 XOR 運算子 Self-inverse的成雙成對互相消去的特質。


Reference:

[1] undefined - Missing Number - LeetCode

留言
avatar-img
留言分享你的想法!
avatar-img
小松鼠的演算法樂園
95會員
427內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
2024/10/06
題目敘述 Rank Transform of an Array 給定一個陣列arr,請根據數字的大小給予序號,序號值介於1~len( set(arr) )之間。 最大的數字給予最大的序號。 次大的數字給予次大的序號。 ...依此類推 最小的數字給予最小的序號1。
Thumbnail
2024/10/06
題目敘述 Rank Transform of an Array 給定一個陣列arr,請根據數字的大小給予序號,序號值介於1~len( set(arr) )之間。 最大的數字給予最大的序號。 次大的數字給予次大的序號。 ...依此類推 最小的數字給予最小的序號1。
Thumbnail
2024/10/01
題目敘述 Check If Array Pairs Are Divisible by k 給定一個長度為偶數的整數陣列arr,和一個整數k 。 我們想把陣列元素兩兩一組組成pair,使得每個pair的總和可以被k整除。 如果做得到,返回True。 如果不行,返回False。
Thumbnail
2024/10/01
題目敘述 Check If Array Pairs Are Divisible by k 給定一個長度為偶數的整數陣列arr,和一個整數k 。 我們想把陣列元素兩兩一組組成pair,使得每個pair的總和可以被k整除。 如果做得到,返回True。 如果不行,返回False。
Thumbnail
2024/09/29
My Calendar II 給定一個行事曆的class定義和行程安排的介面。 請完成下列function 1.建構子MyCalendarTwo() 2.boolean book(int start, int end) 在行事曆加入一項新行程,起始時間為start, 結束時間為end。
Thumbnail
2024/09/29
My Calendar II 給定一個行事曆的class定義和行程安排的介面。 請完成下列function 1.建構子MyCalendarTwo() 2.boolean book(int start, int end) 在行事曆加入一項新行程,起始時間為start, 結束時間為end。
Thumbnail
看更多
你可能也想看
Thumbnail
TOMICA第一波推出吉伊卡哇聯名小車車的時候馬上就被搶購一空,一直很扼腕當時沒有趕緊入手。前陣子閒來無事逛蝦皮,突然發現幾家商場都又開始重新上架,價格也都回到正常水準,估計是官方又再補了一批貨,想都沒想就立刻下單! 同文也跟大家分享近期蝦皮購物紀錄、好用推薦、蝦皮分潤計畫的聯盟行銷!
Thumbnail
TOMICA第一波推出吉伊卡哇聯名小車車的時候馬上就被搶購一空,一直很扼腕當時沒有趕緊入手。前陣子閒來無事逛蝦皮,突然發現幾家商場都又開始重新上架,價格也都回到正常水準,估計是官方又再補了一批貨,想都沒想就立刻下單! 同文也跟大家分享近期蝦皮購物紀錄、好用推薦、蝦皮分潤計畫的聯盟行銷!
Thumbnail
每年4月、5月都是最多稅要繳的月份,當然大部份的人都是有機會繳到「綜合所得稅」,只是相當相當多人還不知道,原來繳給政府的稅!可以透過一些有活動的銀行信用卡或電子支付來繳,從繳費中賺一點點小確幸!就是賺個1%~2%大家也是很開心的,因為你們把沒回饋變成有回饋,就是用卡的最高境界 所得稅線上申報
Thumbnail
每年4月、5月都是最多稅要繳的月份,當然大部份的人都是有機會繳到「綜合所得稅」,只是相當相當多人還不知道,原來繳給政府的稅!可以透過一些有活動的銀行信用卡或電子支付來繳,從繳費中賺一點點小確幸!就是賺個1%~2%大家也是很開心的,因為你們把沒回饋變成有回饋,就是用卡的最高境界 所得稅線上申報
Thumbnail
題目敘述 題目會給定我們一個n值,要求我們列出從0 ~ n 之間,每個整數有幾個bit1,以陣列的形式返回答案。 例如n=3時 因為 0 = 0b 0 1 = 0b 1 2 = 0b 10 3 = 0b 11 輸出答案為[0, 1, 1, 2] 題目的原文敘述 測試範例 E
Thumbnail
題目敘述 題目會給定我們一個n值,要求我們列出從0 ~ n 之間,每個整數有幾個bit1,以陣列的形式返回答案。 例如n=3時 因為 0 = 0b 0 1 = 0b 1 2 = 0b 10 3 = 0b 11 輸出答案為[0, 1, 1, 2] 題目的原文敘述 測試範例 E
Thumbnail
題目敘述 題目會給定一個整數陣列nums,原本裡面包含有整數1到n,但是中間不小心出了差錯,導致有一個數字消失了,而另一個數字重複了。 請找出重複的數字以及消失的數字,並且 以陣列的形式[重複的數字, 消失的數字]返回這兩個數字。 例如: [1,3,3,4] 消失的數字是2,重複的數字是
Thumbnail
題目敘述 題目會給定一個整數陣列nums,原本裡面包含有整數1到n,但是中間不小心出了差錯,導致有一個數字消失了,而另一個數字重複了。 請找出重複的數字以及消失的數字,並且 以陣列的形式[重複的數字, 消失的數字]返回這兩個數字。 例如: [1,3,3,4] 消失的數字是2,重複的數字是
Thumbnail
題目敘述 題目會告訴我們一組英文和數字之間的轉換編碼規則,還有一個輸入字串s,問我總共有多少合法的解碼方式? 要特別留意,輸入字串可能包含有leading zero,導致無法解碼。 轉換規則如下: A <-> 1 B <-> 2 C <-> 3 ... Z <-> 26 詳細的題
Thumbnail
題目敘述 題目會告訴我們一組英文和數字之間的轉換編碼規則,還有一個輸入字串s,問我總共有多少合法的解碼方式? 要特別留意,輸入字串可能包含有leading zero,導致無法解碼。 轉換規則如下: A <-> 1 B <-> 2 C <-> 3 ... Z <-> 26 詳細的題
Thumbnail
題目會給我們一個字串陣列nums,內容都是二進位字串,要求我們造出一個另一個相等長度,新的二進位字串,而且不和字串陣列nums內的重複。 答案可能有不只一組,回傳合任一組合法的答案皆可。
Thumbnail
題目會給我們一個字串陣列nums,內容都是二進位字串,要求我們造出一個另一個相等長度,新的二進位字串,而且不和字串陣列nums內的重複。 答案可能有不只一組,回傳合任一組合法的答案皆可。
Thumbnail
題目會給定我們一個陣列,要求我們重新安排順序,把等於零的數字搬到後面。 同時必須保持原本數字的前後相對次序。
Thumbnail
題目會給定我們一個陣列,要求我們重新安排順序,把等於零的數字搬到後面。 同時必須保持原本數字的前後相對次序。
Thumbnail
題目會給定我們一個陣列,並且定義了一種三角形合併的操作。 當下這一排相鄰的兩項相加,對mod 10取餘數,會成為下一排的對應項,一直反覆操作,直到剩下一個元素為止。 要求我們返回最後一層的答案。 測試範例: Example 1: Input: nums = [1,2,
Thumbnail
題目會給定我們一個陣列,並且定義了一種三角形合併的操作。 當下這一排相鄰的兩項相加,對mod 10取餘數,會成為下一排的對應項,一直反覆操作,直到剩下一個元素為止。 要求我們返回最後一層的答案。 測試範例: Example 1: Input: nums = [1,2,
Thumbnail
題目會給定一個陣列,長度為n,裡面的數字都是獨一無二,落在0~n的範圍。 要求我們找出那個不見的數字 Missing Number 註: (n+1)個數字,無法同時放入n個不同的格子,必定有一個數字不見了。
Thumbnail
題目會給定一個陣列,長度為n,裡面的數字都是獨一無二,落在0~n的範圍。 要求我們找出那個不見的數字 Missing Number 註: (n+1)個數字,無法同時放入n個不同的格子,必定有一個數字不見了。
Thumbnail
題目會給定一個陣列,每個數字都恰好出現兩次,只有一個數字是例外。 要求我們找出那個落單也就是例外的數字。
Thumbnail
題目會給定一個陣列,每個數字都恰好出現兩次,只有一個數字是例外。 要求我們找出那個落單也就是例外的數字。
Thumbnail
題目會給我們一個輸入陣列candidates,和一個目標值 target 問我們,從canditdates裡面重複挑選,可以湊出總和為target目標值的組合數有幾種? 在此,我們將使用找零錢II的DP模型和化簡的技巧來解題。
Thumbnail
題目會給我們一個輸入陣列candidates,和一個目標值 target 問我們,從canditdates裡面重複挑選,可以湊出總和為target目標值的組合數有幾種? 在此,我們將使用找零錢II的DP模型和化簡的技巧來解題。
Thumbnail
題目會給我們一個輸入陣列,長度為n+1。 陣列裡面會有n+1個數字,數字的範圍從1到n 裡面恰好有一個數字重複出現,要求我們找出那個重複的數字。 題目要求只能使用常數空間O(1),並且限制不能修改陣列內容。
Thumbnail
題目會給我們一個輸入陣列,長度為n+1。 陣列裡面會有n+1個數字,數字的範圍從1到n 裡面恰好有一個數字重複出現,要求我們找出那個重複的數字。 題目要求只能使用常數空間O(1),並且限制不能修改陣列內容。
追蹤感興趣的內容從 Google News 追蹤更多 vocus 的最新精選內容追蹤 Google News