幹你老師，打到一半閃退，全部都不見了 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-web.org.tw), 來自: 42.72.109.58 (臺灣) ※ 文章網址: https://ptt-web.org.tw/Marginalman/M.1711361734.A.118

→ JenniferLope: 大師 03/25 18:16

→ digua: 大師 03/25 18:16

→ yam276: 大師 03/25 18:16

→ wwndbk: 大師 03/25 18:19

→ oinishere: 大師 03/25 18:29

推 Muzaffer: 身邊有朋友被包養嗎 03/25 18:29

→ sustainer123: 大師 03/25 18:33

→ Rushia: 第一個不行吧 03/25 18:43