幹你老師，打到一半閃退，全部都不見了
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
}