Re: [閒聊] 每日leetcode已回收
幹你老師，打到一半閃退，全部都不見了
287. Find the Duplicate Number
有一個矩陣nums，長度為n+1，矩陣元素大小介於[1,n]
矩陣內有一個數字會重複出現，請問該數字是多少？
題目限制：不能修改原本的矩陣、只能使用constant extra space
思路
1.用一個大小為n的矩陣去紀錄每個數字出現的頻率，出現超過1次的就是答案
2.用二分搜尋法，去尋找值小於等於中間值m=1+(n-1)/2的元素個數(cnt)
(1)如果cnt<=m，代表重複的值在m+1~n
(2)如果cnt>m，代表重複的值在1~m
就這樣一直重複下去就能找到答案了
3.用bit manupulation，計算nums內的元素第i個bit為1的數量(a)
以及1~n在第1個bit為1個數量(b)
若a>b則重複的數字的第i個bit為1反之為0
4.因為只有一個數字重複所以會存在一個環，用快慢指標的概念，去尋找環的起點
這個比較難解釋，建議去看影片，比較好理解
golang code
func findDuplicate(nums []int) int {
ptr1,ptr2:=0,0
for{
ptr1=nums[ptr1]
ptr2=nums[nums[ptr2]]
if ptr1==ptr2{
break
}
}
ptr1=0
for ptr1!=ptr2{
ptr1=nums[ptr1]
ptr2=nums[ptr2]
}
return ptr1
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.72.109.58 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1711361734.A.118.html
→
03/25 18:16,
1年前
, 1F
03/25 18:16, 1F
→
03/25 18:16,
1年前
, 2F
03/25 18:16, 2F
→
03/25 18:16,
1年前
, 3F
03/25 18:16, 3F
→
03/25 18:19,
1年前
, 4F
03/25 18:19, 4F
→
03/25 18:29,
1年前
, 5F
03/25 18:29, 5F
→
03/25 18:33,
1年前
, 6F
03/25 18:33, 6F
→
03/25 18:43,
1年前
, 7F
03/25 18:43, 7F
討論串 (同標題文章)
完整討論串 (本文為第 70 之 1548 篇)：