给定一个只包含整数的有序数组 nums ,每个元素都会出现两次,唯有一个数只会出现一次,请找出这个唯一的数字。
示例 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 <= 105
0 <= nums[i] <= 105
进阶: 采用的方案可以在 O(log n) 时间复杂度和 O(1) 空间复杂度中运行吗?
注意:本题与主站 540 题相同:
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题目,题目同leetcode 540.有序数组中的单一元素
页面更新:2024-04-28
本站资料均由网友自行发布提供,仅用于学习交流。如有版权问题,请与我联系,QQ:4156828
© CopyRight 2020-2024 All Rights Reserved. Powered By 71396.com 闽ICP备11008920号-4
闽公网安备35020302034903号