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

题目描述

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

image-20230312175831136

思路分析

解法一：暴力枚举 解法二：二分查找 由于数组是有序的，可以使用二分查找的思想，每次找到中间的数，判断它是否为单一元素，如果不是，则判断它左右两边的元素个数是否为奇数，如果是，则单一元素在左边，否则在右边。 解法三：异或运算

参考代码

1

write your code here

🍏 点击查看 Java 题解

1
2
3
4
5
6
7
8
9

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            // 确保mid在偶数位置，使得判断条件一直在偶数位置和奇数位置进行比较
            if (mid % 2 == 1) {
                mid--;
            }
            // 如果mid与下一个元素不相等，说明单一元素在mid的左侧
            if (nums[mid] != nums[mid + 1]) {
                right = mid;
            } else {
                // 否则，单一元素在mid的右侧
                left = mid + 2;
            }
        }
        return nums[left];
    }
}
本文作者:
本文链接: https://hgnulb.github.io/blog/00553978
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！