YSMull
<-- algorithm



原题链接

题目描述

升序数组,每个数组元素出现了两次,只有一个出现了一次,把这个数字揪出来。要求时间复杂度是log(n)

分析

这个复杂度,肯定需要二分,当我们求出 mid 的值之后,接下来怎样进一步的确定在左边还是在右边,是需要思考的。
方法是,二分之后,mid 如果有重复的,那么 mid 跟与它相同的数一起消掉后,数组被分成了两个部分,target 应该出现在长度为奇数的那半边。

实现

递归写法:

class Solution {
    public int singleNonDuplicate(int[] nums) {
        return singleNonDuplicate(nums, 0, nums.length - 1);
    }

    public int singleNonDuplicate(int[] nums, int i, int j) {
        if (i == j) {
            return nums[i];
        }
        int mid = (i + j) / 2;
        int l = nums[mid - 1], m = nums[mid], r = nums[mid + 1];
        if (l != m && m != r) return m;
        if (l == m) { // 跟左边的消了
            if ((mid - 2 - i + 1) % 2 == 0) { // 左边是偶数个,所以在右边
                return singleNonDuplicate(nums, mid + 1, j);
            } else {
                return singleNonDuplicate(nums, i, mid - 2);
            }
        } else {
            if ((j - (mid + 2) + 1) % 2 == 0) { // 右边是偶数个,所以在左边
                return singleNonDuplicate(nums, i, mid - 1);
            } else {
                return singleNonDuplicate(nums, mid + 2, j);
            }
        }
    }
}

由于递归的空间复杂度比较高,用 while 循环改写一下,也比较简单:

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int i = 0, j = nums.length - 1;
        while (true) {
            if (i == j) return nums[i];
            int mid = (i + j) / 2;
            int l = nums[mid - 1], m = nums[mid], r = nums[mid + 1];
            if (l != m && m != r) return m;
            if (l == m) { // 跟左边的消了
                if ((mid - 2 - i + 1) % 2 == 0) { // 左边是偶数个,所以在右边
                    i = mid + 1;
                } else {
                    j = mid - 2;
                }
            } else {
                if ((j - (mid + 2) + 1) % 2 == 0) { // 右边是偶数个,所以在左边
                    j = mid - 1;
                } else {
                    i = mid + 2;
                }
            }
        }
    }
}