【leetcode】【剑指offer Ⅱ】070. 排序数组中只出现一次的数字

问题描述：

• 给定一个只包含整数的有序数组 nums，每个元素都会出现两次，唯有一个数只会出现一次，请找出这个唯一的数字。
• 设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。

核心思路：

• 该题关键在于有序，因此可以用二分搜索来解决。【如果不是有序，则直接用异或操作即可】
  • 该题的二分搜索关键在于根据 mid 位置的奇偶性及其前后的数值相等情况来进行判断区间的缩减。
  • 因为原数组是有序的，所以相同的两个元素必定相邻，假设只出现一次的元素索引位置为 i，则 [0, i-1] 的区间内，偶数索引 j 上的值必定等于 j+1 上的值；同理，[i+1, nums.size()-1] 的区间内，奇数索引 k 上的值必定等于 k+1 上的值。
• 利用位运算可以简化判断代码，具体看代码。

代码实现：

• 二分搜索解法代码实现如下：

  class Solution
  {
  public:
      int singleNonDuplicate(vector<int>& nums)
      {
          int m = nums.size();
          int l = 0, r = m-1;
          int mid;
          while(l < r)
          {
              mid = l + (r - l)/2;
              if(mid % 2 == 0)
              {
                  if(mid == m-1 or nums[mid] != nums[mid+1])
                      r = mid;
                  else l = mid + 1;
              }
              else
              {
                  if(nums[mid] != nums[mid-1])
                      r = mid;
                  else l = mid + 1;
              }
          }
          return nums[l];
      }
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27

• 官方题解代码实现如下：【思路一样，用位运算简化了奇偶判断】

  class Solution {
  public:
      int singleNonDuplicate(vector<int>& nums) {
          int low = 0, high = nums.size() - 1;
          while (low < high) {
              int mid = (high - low) / 2 + low;
              if (nums[mid] == nums[mid ^ 1]) { // 要理解该式子，只需要将 mid 代入偶数或奇数即可
                  low = mid + 1;
              } else {
                  high = mid;
              }
          }
          return nums[low];
      }
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15