Re: [閒聊] 每日LeetCode

[Rushia (みけねこ的鼻屎)]

540. Single Element in a Sorted Array
給你一個已排序整數陣列，裡面的所有數字都有恰好兩個，只有一個數字只有一個，
找出這個數字是什麼，限制時間複雜度：O(logn)且空間複雜度：O(1)。

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.看到題目說"陣列已排序"和"時間複雜度O(logn)"就可以確定這題要用二元搜尋來
  做了，問題是我們要怎麼樣才能每次查找都捨棄掉一半不必去查的資料。

2.首先做個邊界處理，n == 1 的時候直接返回。

3.把mid作為切點，檢查當前mid這個索引數字的左右兩邊，如果有重複數字就返回兩
  個重複數字的索引，否則直接返回nums[mid]。

4.要判斷要往左邊找還是右邊找的條件是：判斷某一半邊的元素數量是否是偶數
  舉例來說，若index=[3,4]

  1 1 2 3 3 4 4

  因為所有數字恰好兩個且只有一個數字只有一個，所以一定有一邊有奇數個元素
  所以去除當前重複元素之後的半邊如果有奇數個元素就往那邊找，另一邊捨棄。

5.最後返回nums[l]即可


JavaCode：
---------------------------------
class Solution {
    public int singleNonDuplicate(int[] nums) {
        int n = nums.length;
        if (n < 2) {
            return nums[0];
        }
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = (l + r) / 2;
            int[] index = getIndex(nums, mid);
            if (index.length == 1) {
                return nums[mid];
            } else if ((index[0] - l) % 2 == 1) {
                r = index[0] - 1;
            } else {
                l = index[1] + 1;
            }
        }
        return nums[l];
    }

    private int[] getIndex(int[] nums, int i) {
        int n = nums.length;
        if (i > 0 && nums[i] == nums[i - 1]) {
            return new int[]{i - 1, i};
        }
        if (i + 1 < n && nums[i] == nums[i + 1]) {
            return new int[]{i, i + 1};
        }
        return new int[]{i};
    }
}
---------------------------------

二元搜尋好難 我寫的時候一直邊界炸掉 插滴

--
https://i.imgur.com/uiFto42.jpg

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.231.18.126 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1676951805.A.8F4.html
※ 編輯: Rushia (36.231.18.126 臺灣), 02/21/2023 11:57:39
推 DDFox: 大師
推 Che31128: 大師
推 abcd991276: 大師
推 NTHUlagka: 大師 想問一下為什麼長度=1時直接回傳0阿 而不是nums[
→ NTHUlagka: 0]
靠北 貼到我第一次WA的程式碼 修正了
※ 編輯: Rushia (36.231.18.126 臺灣), 02/21/2023 12:25:11
推 NTHUlagka: 是說你那個判斷不加應該也沒差 底下的二分搜還是能找
→ NTHUlagka: 到答案
→ NTHUlagka: XD想說原來長度1的測資答案剛好是0阿
→ NTHUlagka: 喔喔說錯沒跑二分直接回傳nums[l]就是
推 idiont: 沒有那個判斷 底下檢查會超出邊界 應該是必要的
→ idiont: 沒事 原來有檢查 那應該沒差
推 NTHUlagka: 不會吧 沒那個判斷就不會進入二分搜尋了 因為l==r
→ NTHUlagka: 可能也不需要檢查雙向 我是只有判斷單向 你另一邊會在
→ NTHUlagka: 之後被檢查到
→ Rushia: 對不起 我二元搜尋超爛
推 NTHUlagka: 沒 樓主大師
推 dustsstar79: 大師
推 Mustafar: 何必二分搜？對每個元素，檢查是否與前後相等
推 NTHUlagka: 樓上因為題目要求
→ idiont: 就算題目沒要求 有個執行速度更快的做法也沒不好吧
推 Mustafar: 好好笑我 O(N) 的解 Beats 97.22%
→ Mustafar: 原因也不難猜，大概就因為計算機結構提到的 cache miss
→ Mustafar: 順向的掃過去 cache 都可以命中，二分搜跳來跳去實務上
→ Mustafar: 一定比較快
推 idiont: https://i.imgur.com/4FfwXNl.jpg 還好我的二分搜還是快了
→ idiont: 一點 O(N)會過也只是題目的N不夠大吧
推 Mustafar: N <= 1e6 時 O(N) 本來就夠快啊，除非 1e9 甚至 1e18
→ Mustafar: 才會一定要 O(log N) 甚至 O(1)
推 NTHUlagka: M大的想法蠻有趣的 如果leetcode執行速度真的與cache
→ NTHUlagka: miss有關, 那這樣之後遇到的題目如果限制是10^8, 不知
→ NTHUlagka: 道是否能用O(n)的解法解 感覺是值得嘗試
推 NTHUlagka: 不知道能不能將cache miss量化, 不然這樣很難估實際的
→ NTHUlagka: 複雜度
推 Mustafar: 不過我自己是覺得 LeetCode 的時間本來就很不準
→ Mustafar: 之前現場比賽 N=1e4 我們也是想很久亂丟 O(N^2) 結果 AC