leetcode 540. Single Element in a Sorted Array

末蓝、 2022-06-08 02:51 236阅读 0赞

1.题目

Given a sorted array consisting of only integers where every element appears twice except for one element which appears once. Find this single element that appears only once.
一个有序的整型数组，除一个元素只出现一次外，其余元素均出现两次。找出这个只出现一次的元素。
要求：时间复杂度O(logn),空间复杂度O(1)
Example 1:
Input: [1,1,2,3,3,4,4,8,8]
Output: 2
Example 2:
Input: [3,3,7,7,10,11,11]
Output: 10

2.分析

时间复杂度要求O(logn)，可以选用二分查找。

观察数组可以发现这样一个规律：对于数组S
在只出现一次的元素A出现之前，所有S[2*i]=S[2*i+1]
我们可以依据这一规律来判断A在当前位置的左边还是右边。

3.代码

  1. class Solution {
  2. public:
  3.     int singleNonDuplicate(vector<int>& nums) {
  4.         int left = 0, right = nums.size() / 2;
  5.         while (left < right) {
  6.             int mid = left + (right - left) / 2;
  7.             if (nums[mid * 2] != nums[mid * 2 + 1])
  8.                 right = mid;
  9.             else
  10.                 left = mid + 1;
  11.         }
  12.         return nums[left * 2];
  13.     }
  15. };

发表评论

表情：
评论列表 （有 0 条评论，236人围观）

还没有评论，来说两句吧...

相关阅读