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];
};

參考資料