当前位置：首页 > article >正文

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

article 2025/3/4 15:44:57

给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。

请你找出并返回只出现一次的那个数。

你设计的解决方案必须满足 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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/single-element-in-a-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

写了几个样例在纸上找了下规律，找到规律之后遍摸清楚了每一步需要判断的边界，例子如下：

有这样一个数组： 1 1 2 2 3 3 4 5 5 6 6 7 7 8 8

对应位置的下标： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

经观察可以发现：

1> 在我们要找的数字之前：

奇数索引位置与其前一个位置的数值相等;
偶数索引位置与其后一个位置的数值相等;

2> 在我们要找的数字之后：

奇数索引位置与其后一个位置的数值相等;
偶数索引位置与其前一个位置的数值相等;

既然发现了规律我们就能判断目标位置在当前mid左侧还是右侧，首先判断当前mid是奇索引还是偶索引，如果是奇索引就判断其与前一个位置是否相等，如果相等，说明mid在目标位置左侧，反之在右侧。如果是偶索引，就判断其与后一个位置的数值是否相等，相等，说明mid在目标位置左侧，反之在右侧，直至跳出循环。

思路是这样，但写出代码之后有一些特殊情况并未考虑，导致有的测试用例无法通过，根据观察，有以下几种情况，有时是单一元素出现在数组边界，即最左侧和最右侧，有时是最中间，通过一步步改代码判断这些特殊情况，最后是全部通过，但比较麻烦也不好记忆，题解的方法貌似规避了这种问题。

代码如下：

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int l = 0;
        int h = nums.length - 1;
        while (l <= h) {
            int mid = l + (h - l) / 2;
            if (mid % 2 == 0) {
                if (mid == h || mid == l) {
                    return nums[mid];
                }
                if (nums[mid] == nums[mid + 1]) {
                    l = mid + 1;
                } else {
                    if (nums[mid] != nums[mid - 1]) {
                        return nums[mid];
                    }
                    h = mid - 1;
                }
            } else {
                if (mid == l) {
                    if (mid == 0)
                        return nums[l];
                }
                if (nums[mid] == nums[mid - 1]) {
                    l = mid + 1;
                } else {
                    h = mid - 1;
                }
            }
        }
        return nums[l];
    }
}

方法二：

每次都判断偶数位置，如果是奇数就-1将其变成偶数位置，那么要考虑的情况就少了很多，只需判断当前位置和下一位置是否相等，相等则在目标位置左侧，不等则在右侧。

代码如下：

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int l = 0;
        int h = nums.length - 1;
        if (h == 0) {
            return nums[0];
        }
        while (l <= h) {
            int mid = l + (h - l) / 2;
            if (mid % 2 != 0) {
                mid -= 1;
            }
            if(mid==nums.length-1){
                return nums[mid];
            }
            if (nums[mid] == nums[mid + 1]) {
                l = mid + 2;
            } else {
                h = mid - 1;
            }
        }
        return nums[l];
    }
}

这种写法还是有很多判断，要减少那些判断，可以将答案锁定在l出现的位置，那么将while循环设置为（l<h）就一定出现在l位置，同时也避免了要判断数组溢出的情况

代码如下：

public int singleNonDuplicate(int[] nums) {
    int l = 0, h = nums.length - 1;
    while (l < h) {
        int m = l + (h - l) / 2;
        if (m % 2 == 1) {
            m--;   // 保证 l/h/m 都在偶数位，使得查找区间大小一直都是奇数
        }
        if (nums[m] == nums[m + 1]) {
            l = m + 2;
        } else {
            h = m;
        }
    }
    return nums[l];
}

查看全文

http://www.kler.cn/a/13871.html