「每日LeetCode」2022年2月14日

本文最后更新于：2023年3月19日 晚上

540.有序数组中的单一元素

540.有序数组中的单一元素

Category Difficulty Likes Dislikes
algorithms Medium (58.46%) 362 -

Tags
Companies
给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。
请你找出并返回只出现一次的那个数。
你设计的解决方案必须满足 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 <= 105
  • 0 <= nums[i] <= 105

思路

二分查找，并判断当前的下标，如果当前元素和前一个元素相同，且下标为偶数，说明要找的元素在左边，否则在右边。如果和后一个元素相同，切下标为奇数，说明要找的元素在左边，否则在右边。

解答

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
28
29
30
/*
 * @lc app=leetcode.cn id=540 lang=javascript
 *
 * [540] 有序数组中的单一元素
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNonDuplicate = function (nums) {
  let left = 0,
    right = nums.length - 1;
  while (left <= right) {
    const mid = Math.round((left + right) / 2);
    const num = nums[mid],
      before = nums[mid - 1],
      after = nums[mid + 1];
    if (num !== before && num !== after) return num;
    else if (num === before) {
      if (mid % 2 === 0) right = mid - 1;
      else left = mid + 1;
    } else if (num === after) {
      if (mid % 2 === 0) left = mid + 1;
      else right = mid - 1;
    }
  }
};
// @lc code=end