leetcode540_go_有序數組中的單一元素

題目

給定一個只包含整數的有序數組，每個元素都會出現兩次，唯有一個數只會出現一次，找出這個數。

示例 1:輸入: [1,1,2,3,3,4,4,8,8]輸出: 2

示例 2:輸入: [3,3,7,7,10,11,11]輸出: 10

注意: 您的方案應該在 O(log n)時間複雜度和 O(1)空間複雜度中運行。

解題思路分析

1、遍歷；時間複雜度O(n)，空間複雜度O(1)

func singleNonDuplicate(nums []int) int { for i := 0; i < len(nums)-1; i = i + 2 { if nums[i] != nums[i+1] { return nums[i] } } return nums[len(nums)-1]}

2、二分查找；時間複雜度O(log(n))，空間複雜度O(1)

func singleNonDuplicate(nums []int) int { n := len(nums) left, right := 0, n-1 for left < right { mid := left + (right-left)/2 if mid%2 == 1 { mid-- } if nums[mid] == nums[mid+1] { left = mid + 2 } else { right = mid } } return nums[left]}

3、異或；時間複雜度O(n)，空間複雜度O(1)

func singleNonDuplicate(nums []int) int { res := 0 for i := 0; i < len(nums); i++ { res = res ^ nums[i] } return res}

總結

Medium題目，O(log(n))時間複雜度使用二分查找