540. 有序数组中的单一元素
程序员文章站
2024-03-17 17:14:28
...
540. 有序数组中的单一元素
1.题目描述
给定一个只包含整数的有序数组,每个元素都会出现两次,唯有一个数只会出现一次,找出这个数。
示例 1:
示例 2:
注意: 您的方案应该在 O(log n)时间复杂度和 O(1)空间复杂度中运行。
2.思路(二分法)
1.令 index 为 Single Element 在数组中的位置。在 index 之后,数组中原来存在的成对状态被改变。如果 mid = left + (right - left) / 2 为偶数,并且 mid + 1 < index,那么 nums[mid] == nums[mid + 1];如果m + 1 >= index,那么 nums[mid] != nums[mid + 1]。
2.所以,如果 nums[mid] == nums[mid + 1],那么 index 所在的数组位置为 [mid + 2, right],此时令 left = mid + 2;如果 nums[mid] != nums[mid + 1],那么 index 所在的数组位置为 [left, mid],此时令 right = mid。
3.一旦 left == right,则当前搜索空间为 1 个元素,那么该元素为单个元素,我们将返回它。
3.代码
class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
int left = 0,right = nums.size() - 1;
while(left < right){
int mid = left + (right - left) / 2;
if(mid % 2 == 1){//保证m为偶数
mid--;
}
if(nums[mid] == nums[mid+1]){//说明nums[mid]在目标的右边
left = mid + 2;
}
else{
right = mid;//说明nums[mid]在目标的左边
}
}
return nums[left];
}
};
4.复杂度分析
时间复杂度:O(logn)
空间复杂度:O(1)
上一篇: 强化学习之动态规划
推荐阅读
-
540. 有序数组中的单一元素
-
二分查找.540. 有序数组中的单一元素
-
编写一个函数,返回数组元素中最大值的地址,并在主函数中输出该元素。说明:主函数中的代码不能修改。
-
LeetCode540——有序数组中的单一元素(二分法)
-
540 有序数组中的单一元素(找规律、二分查找)
-
LeetCode #540 有序数组中的单一元素 二分查找
-
34. 在排序数组中查找元素的第一个和最后一个位置
-
540. 有序数组中的单一元素——二分查找
-
LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置 Find First and Last Position of Element in Sorted Array(C语言)
-
二分法查找,返回有序数组中第一个大于给定值的元素的索引