540. Single Element in a Sorted Array

Leetcode 问题: 540. Single Element in a Sorted Array
Categories:
Tags:

题目

You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once.

Return the single element that appears only once.

Your solution must run in O(log n) time and O(1) space.

传入一个排序好的整数阵列 nums，整数阵列中每个整数都是两两一组 但其中只有一个数字是单独存在的，找出那个数字是多少

Example

Input: nums = [1,1,2,3,3,4,4,8,8]
Output: 2

Input: nums = [3,3,7,7,10,11,11]
Output: 10

演算法

1. 二分法切割要检查的数字索引范围

设定左右指标，匡选检查的范围

  • 左边指标: 0，数字阵列最左方索引
  • 右边指标: 数字阵列最右方索引

取左右指标索引，左右逼近到可能出现的最接近的数字，如果「左边数字索引」与「右边数字索引」没有相交，表示还可以再寻找

将数字索引位置切割成一半，拿左右字母索引的平均数当作切割点，可以把数字切割成一半，减少要检查的范围

2. 确认中间参考指标在偶数位置

因为索引从 0 开始，然后所有的数字都是成对的，所以偶数索引为成对数字的第 1 个数字

确保「参考指标」指向的是成对数字的第 1 个数字

如果「中间参考指标」是「奇数索引位置」，将指标往左移动，让指标变成「偶数索引位置」

3. 比较中间参考指标左右成对数字

状况 A. 「中间参考指标」左右数字相等，所以这个是成对的数字

「中间参考指标」是在「偶数索引位置」，所以表示「中间参考指标」左方的数字数量也是偶数个

以「数字阵列」的规则，如果是「偶数」阵列数字，表示前面的数字也一定是成对的，不需要再检查左边数字

需要往「中间参考指标」右边检查，将「左指标」往右移动 2 格，跳离目前「中间参考指标」的两个成对数字

状况 B. 「中间参考指标」左右数字不相等，所以这个不是成对的数字

「中间参考指标」是在「偶数索引位置」，所以表示「中间参考指标」左方的数字数量也是偶数个

但因为「中间参考指标」左右两个数字是不相等的，所以左方一定有一个数字导致数字无法成对

因为左方无法成对相等，所以左方要检查的数字个数为奇数个

需要往「中间参考指标」左边检查，将「右指标」设定为目前「中间参考指标」，让左方数字个数变成奇数个

确保确保「左指标」左边一定是偶数个成对数字

最后左指标指定的数字，为导致无法成对出现的数字

答案

JavaScript

/**
 * @param {number[]} numsList
 * @return {number}
 */
var singleNonDuplicate = function(numsList) {
    // 左指标
    let leftPointer = 0;
    // 右指标
    let rightPointer = numsList.length - 1;

    while (leftPointer < rightPointer) {
        // 当「左指标」还没超过「右指标」，表示还没比完，可以继续比较
        // 将检查的指标切半，用中间指标当作参考指标
        let middlePointer = leftPointer + Math.floor((rightPointer - leftPointer) / 2);

        if (middlePointer % 2 == 1) {
            // 如果「中间参考指标」是「奇数索引位置」，将指标往左移动，让指标变成「偶数索引位置」
            // 确保「参考指标」指向的是成对数字的第 1 个数字（索引从 0 开始，所以偶数索引为第 1 个数字）
            middlePointer--;
        }

        // 「参考指标」成对数字「左方」数字
        let checkLeftNumber = numsList[middlePointer];
        // 「参考指标」成对数字「右方」数字
        let checkRightNumber = numsList[middlePointer + 1];


        if (checkLeftNumber == checkRightNumber) {
            // 因为「中间参考指标」左右数字相等，所以这个是成对的数字
            // 且「中间参考指标」是在「偶数索引位置」，所以表示「中间参考指标」左方的数字数量也是偶数个
            // 以「数字阵列」的规则，如果是「偶数」阵列数字，表示前面的数字也一定是成对的，不需要再检查左边数字
            // 需要往「中间参考指标」右边检查，将「左指标」往右移动 2 格，跳离目前「中间参考指标」的两个成对数字
            leftPointer = middlePointer + 2;
        } else {
            // 因为「中间参考指标」左右数字不相等，所以这个不是成对的数字
            // 且「中间参考指标」是在「偶数索引位置」，所以表示「中间参考指标」左方的数字数量也是偶数个
            // 但因为「中间参考指标」左右两个数字是不相等的，所以左方一定有一个数字导致数字无法成对
            // 因为左方无法成对相等，所以左方要检查的数字个数为奇数个
            // 需要往「中间参考指标」左边检查，将「右指标」设定为目前「中间参考指标」，让左方数字个数变成奇数个
            rightPointer = middlePointer;
        }

    }

    // 因为「左指标」会不断地往右移动，然后一直确保「左指标」左边一定是偶数个成对数字
    // 所以最后左指标指定的数字为导致无法成对出现的数字
    return numsList[leftPointer];
};

参考资料