class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
}
};
剑指 Offer II 070. 排序数组中只出现一次的数字
给定一个只包含整数的有序数组 nums ，每个元素都会出现两次，唯有一个数只会出现一次，请找出这个唯一的数字。
你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。
示例 1:
输入: nums = [1,1,2,3,3,4,4,8,8] 输出: 2
示例 2:
输入: nums = [3,3,7,7,10,11,11] 输出: 10
提示:
1 <= nums.length <= 1050 <= nums[i] <= 105
注意：本题与主站 540 题相同：https://leetcode.cn/problems/single-element-in-a-sorted-array/
原站题解
python3 解法, 执行用时: 48 ms, 内存消耗: 16.8 MB, 提交时间: 2022-11-21 11:25:11
class Solution:
def singleNonDuplicate(self, nums: List[int]) -> int:
low, high = 0, len(nums) - 1
while low < high:
mid = (low + high) // 2
mid -= mid & 1
if nums[mid] == nums[mid + 1]:
low = mid + 2
else:
high = mid
return nums[low]
golang 解法, 执行用时: 0 ms, 内存消耗: 3.8 MB, 提交时间: 2022-11-21 11:24:54
func singleNonDuplicate(nums []int) int {
low, high := 0, len(nums)-1
for low < high {
mid := low + (high-low)/2
mid -= mid & 1
if nums[mid] == nums[mid+1] {
low = mid + 2
} else {
high = mid
}
}
return nums[low]
}
golang 解法, 执行用时: 4 ms, 内存消耗: 3.8 MB, 提交时间: 2022-11-21 11:24:30
func singleNonDuplicate(nums []int) int {
low, high := 0, len(nums)-1
for low < high {
mid := low + (high-low)/2
if nums[mid] == nums[mid^1] {
low = mid + 1
} else {
high = mid
}
}
return nums[low]
}
python3 解法, 执行用时: 28 ms, 内存消耗: 16.8 MB, 提交时间: 2022-11-21 11:24:02
class Solution:
def singleNonDuplicate(self, nums: List[int]) -> int:
low, high = 0, len(nums) - 1
while low < high:
mid = (low + high) // 2
if nums[mid] == nums[mid ^ 1]: # mid为偶数，则+1，反之-1
low = mid + 1
else:
high = mid
return nums[low]