Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.
Note:
- You must not modify the array (assume the array is read only).
- You must use only constant, O(1) extra space.
- Your runtime complexity should be less than
O(n2) . - There is only one duplicate number in the array, but it could be repeated more than once.
這題是要在 array 裡面找到重複的數字
題意就像是,有13個人,一定有2個人的生日月份是重複的
解題想法如下
- 用生日月份來思考,12個月的中間是6月,歷遍一次整個 array,記算生日月份小於6月的有多少人
- 如果人數小於等於 6,那就代表重複的月份一定是在 7 到 12 月,也就是後半年
- 如果人數大於 6,就代表重複的月份一定是在 1 到 6 月,也就是前半年
- 重複以上 binary search,最後的 lower bound 就會是重複的那個月份
這題還有一個很厲害的解法
用到的也是和 Link List Cycle 所使用的演算法 Floyd's Circle Detection Algorithm
因為已經確定 array 裡面有重複數字,可以視作這個 array 有一個迴圈
之前的想法是用指標往前的步數不同來思考
在這題,可以想成是函式對應關係
a = f(X),b = f(X1),c = f(X2) ...
如果有重複的數字,就代表存在 Xi != Xj,f(Xi) = f(Xj)
這邊,把 array[index] 當作函式,而在此 index 的值為 value
所以只要找到 array[index_1] = array[index_2],就是找到迴圈了
然後快慢指針的部分,則可以用
slowIndex = array[slowIndex]
fastIndex = array[array[fastIndex]]
的方式來實現
那要找到重複的數字,其實就是 Link List Cycle II 所要求的迴圈起點
運用同樣的思考方式,把 slowIndex 移回到起始點,然後快慢指針每次都只往前一步
再次相遇的那個數字,就是重複的數字
code 如下(參考資料)
還有一個更直覺的想法
因為題目限制,只會有一個數字重複,用一個set來檢查有沒有重複即可
Kotlin
沒有留言:
張貼留言