LeetCode540-有序数组中的单一元素

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/single-element-in-a-sorted-array/

中文链接：https://leetcode-cn.com/problems/single-element-in-a-sorted-array/

题目详述

给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。

示例 1:

1
2
输入: [1,1,2,3,3,4,4,8,8]
输出: 2

示例 2:

1
2
输入: [3,3,7,7,10,11,11]
输出: 10

注意: 您的方案应该在 O(log n)时间复杂度和 O(1)空间复杂度中运行。

题目详解

运用异或的性质，可以直接以 O(n) 的时间复杂度解决。

1
2
3
4
5
6
7
8
9
10
public class LeetCode_00540 {

    public int singleNonDuplicate(int[] nums) {
        int res = 0;
        for (int num : nums) {
            res ^= num;
        }
        return res;
    }
}

不过本题数组是有序的，“数组+有序”可以很自然地想到二分查找。因为数组中每个元素都会出现两次，唯有一个元素只会出现一次，且数组有序，所以单一元素的下标必然为偶数，其他元素都是成对相邻的。

  • 故每次取 mid = lo + (hi - lo) / 2 时，若 mid 为奇数，让 mid 自减变为偶数，然后比较 nums[mid] 和 nums[mid + 1]（统一形式防止越界）。
  • 若 nums[mid] == nums[mid + 1] ，说明 mid 之前都是元素成对存在的，单个元素在后面。
  • 若 nums[mid] != nums[mid + 1] ，说明单个元素下标不超过 mid。
  • 据此进行二分搜索，缩小可能区间直至区间内只有一个元素，这个元素就是单一元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class LeetCode_00540 {

    public int singleNonDuplicate(int[] nums) {
        // 可能的上下限
        int lo = 0;
        int hi = nums.length - 1;
        // 缩小范围直至只有一个元素
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            // 将奇数下标变为偶数下标
            if ((mid & 1) == 1) {
                --mid;
            }
            if (nums[mid] == nums[mid + 1]) {   // 说明 mid 之前元素都是成对存在的，单个元素在后面
                lo = mid + 2;
            } else {                            // 说明单个元素下标不超过 mid
                hi = mid;
            }
        }
        return nums[lo];
    }
}