YSMull
<-- algorithm



原题链接

2021-04-18 第二次写,模板法

数组长度一定是奇数,奇点只可能是偶数下标。

1  1  2  2  3  3  4  4  5  5  6  7  7  8  8  9  9
0     2     4     6     8     10    12    14    16

可以看到,在奇点的左边,偶数下标都是靠左边的数,在奇点的右边,偶数下标都是靠右边的数。

或者说对于所有偶数下标 $i$,在奇点的左边,都满足

\[\text{N}_i == \text{N}_{i+1}\]

在奇点的右边(包括奇点本身)都满足

\[\text{N}_i \neq \text{N}_{i+1}\]

我们只需要判断,从什么时候开始,偶数下标第一次满足了 $N_i \neq N_{i+1}$ ,那么这个偶数下标就是我们得到的奇点。

二分时去掉最后一个元素,如果没搜到,此时 l 一定指向的是最后这个偶数下标的元素。

impl Solution {
    pub fn check(mid: usize, nums: &Vec<i32>) -> bool {
        return if mid % 2 == 0 {
            nums[mid] != nums[mid + 1]
        } else {
            nums[mid - 1] != nums[mid]
        }
    }
    pub fn single_non_duplicate(nums: Vec<i32>) -> i32 {
        let mut l = 0;
        let mut r = nums.len() - 1;
        while l < r {
            let mut mid = l + (r - l) / 2;
            if Solution::check(mid, &nums) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return nums[l];
    }
}

2021-01-22 第一次写

题目描述

升序数组,每个数组元素出现了两次,只有一个出现了一次,把这个数字揪出来。要求时间复杂度是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;
                }
            }
        }
    }
}