Description
給定一個排序陣列，其中每個元素恰好出現兩次，只有一個元素只出現一次。找出這個只出現一次的元素。要求
O(log n)時間複雜度和O(1)空間複雜度。
Example:
Input: nums = [1,1,2,3,3,4,4,8,8] Output: 2
Intuition#
在單獨元素之前，成對元素的首個出現在偶數索引；在之後，首個出現在奇數索引。利用此規律二分搜尋。
- 陣列長度一定是奇數
- 在單獨元素左邊：
nums[偶數] == nums[偶數+1] - 在單獨元素右邊：這個規律被打破
- 利用這個性質在偶數索引上二分搜尋
Approaches#
1: XOR#
- 概念: 全部 XOR 起來，成對的會互相抵消，剩下的就是答案
- 時間複雜度:
O(n) - 空間複雜度:
O(1)
XOR 程式碼
class Solution {
fun singleNonDuplicate(nums: IntArray): Int {
var result = 0
for (num in nums) {
result = result xor num
}
return result
}
}⭐2: Binary Search#
- 概念: 在偶數索引上二分搜尋，檢查
nums[mid] == nums[mid+1]判斷單獨元素在左邊還是右邊 - 時間複雜度:
O(log n) - 空間複雜度:
O(1)
class Solution {
fun singleNonDuplicate(nums: IntArray): Int {
var left = 0
var right = nums.size - 1
while (left < right) {
var mid = left + (right - left) / 2
// 確保 mid 是偶數索引
if (mid % 2 == 1) mid--
if (nums[mid] == nums[mid + 1]) {
// 成對規律正常，單獨元素在右邊
left = mid + 2
} else {
// 規律被破壞，單獨元素在左邊（含 mid）
right = mid
}
}
return nums[left]
}
}關鍵是確保
mid落在偶數索引上，這樣才能正確判斷成對規律。若mid是奇數，先減 1。
🔑 Takeaways#
- Pattern: 利用索引奇偶性的二分搜尋
- 關鍵技巧: 不是在值上二分，而是利用「成對出現」的索引規律。當
nums[偶數] == nums[偶數+1]時表示這一對正常，單獨元素在更右邊