推 DJYOSHITAKA: 大濕 02/20 18:46
推 JIWP: 大師 02/20 18:48
推 JerryChungYC: 大師 02/20 18:52
※ 引述《JerryChungYC (JerryChung)》之銘言：
: https://leetcode.com/problems/missing-number/
: 268. Missing Number
: 給一個包含[0, n]範圍內不同數字的陣列nums，傳回範圍內唯一缺少的數字
: Example 1:
: Input: nums = [3,0,1]
: Output: 2
: Example 2:
: Input: nums = [0,1]
: Output: 2
: Example 3:
: Input: nums = [9,6,4,2,3,5,7,0,1]
: Output: 8
: Python3 code:
: --------------------------------------------------------
: class Solution:
: def missingNumber(self, nums: List[int]) -> int:
: return (len(nums)*(len(nums)+1)//2) - sum(nums)
: --------------------------------------------------------
: 計算0~n的總和-nums的總和
: 每日的題目是人選的還是隨機的啊
想到之前看過的一招 就是把每個數字換到他對應的 index
index 是 range(n)
nums 是 range(n+1) 少掉某個數字
所以 nums 裡會多一個數字 n 放在少掉的那個 index
ex: n=8 少掉 3 這個數字
index 0 1 2 3 4 5 6 7
value 0 1 2 8 4 5 6 7
流程就是檢查現在的 index i 是不是放數字 i
不是的話就把 nums[i] 丟到 index nums[i]
然後把原來放在 nums[nums[i]] 的數字放在 nums[i]
直到 nums[i] == i (或是 nums[i] == n)
最後看 n 放在哪裡就知道少了哪個數字
Python code:
class Solution:
def missingNumber(self, nums: List[int]) -> int:
n = len(nums)
res = n
for i in range(n):
while i != nums[i] and nums[i] != n:
t = nums[i]
nums[i], nums[t] = nums[t], nums[i]
if nums[i] == n:
res = i
return res
延伸就是像前一篇用 XOR
可以發現排完後 i == nums[i] 只有一組會是 (少掉的數字k, n)
用 a^a == 0, a^0 == a 的性質就可以把全部的 index/value XOR 起來
最後剩下的數字就會是 k^n
再 XOR n 就會是 k 了
所以也不用換位置那麼麻煩直接 XOR 就好
--
蛤?
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.164.150.144 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1708425761.A.482.html