Re: [閒聊] 每日LeetCode已回收

看板Marginalman作者 (みけねこ的鼻屎)時間2年前 (2023/02/21 11:56), 2年前編輯推噓17(17推 0噓 18→)
留言35則, 8人參與, 2年前最新討論串244/719 (看更多)
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
推
02/21 11:58, 2年前 , 1F
大師
02/21 11:58, 1F
推
02/21 11:59, 2年前 , 2F
大師
02/21 11:59, 2F
推
02/21 12:03, 2年前 , 3F
大師
02/21 12:03, 3F
推
02/21 12:23, 2年前 , 4F
大師 想問一下為什麼長度=1時直接回傳0阿 而不是nums[
02/21 12:23, 4F
→
02/21 12:23, 2年前 , 5F
0]
02/21 12:23, 5F
靠北 貼到我第一次WA的程式碼 修正了 ※ 編輯: Rushia (36.231.18.126 臺灣), 02/21/2023 12:25:11
推
02/21 12:37, 2年前 , 6F
是說你那個判斷不加應該也沒差 底下的二分搜還是能找
02/21 12:37, 6F
→
02/21 12:37, 2年前 , 7F
到答案
02/21 12:37, 7F
→
02/21 12:38, 2年前 , 8F
XD想說原來長度1的測資答案剛好是0阿
02/21 12:38, 8F
→
02/21 12:40, 2年前 , 9F
喔喔說錯沒跑二分直接回傳nums[l]就是
02/21 12:40, 9F
推
02/21 12:50, 2年前 , 10F
沒有那個判斷 底下檢查會超出邊界 應該是必要的
02/21 12:50, 10F
→
02/21 12:50, 2年前 , 11F
沒事 原來有檢查 那應該沒差
02/21 12:50, 11F
推
02/21 12:51, 2年前 , 12F
不會吧 沒那個判斷就不會進入二分搜尋了 因為l==r
02/21 12:51, 12F
→
02/21 12:52, 2年前 , 13F
可能也不需要檢查雙向 我是只有判斷單向 你另一邊會在
02/21 12:52, 13F
→
02/21 12:52, 2年前 , 14F
之後被檢查到
02/21 12:52, 14F
→
02/21 13:17, 2年前 , 15F
對不起 我二元搜尋超爛
02/21 13:17, 15F
推
02/21 13:42, 2年前 , 16F
沒 樓主大師
02/21 13:42, 16F
推
02/21 14:03, 2年前 , 17F
大師
02/21 14:03, 17F
推
02/21 17:25, 2年前 , 18F
何必二分搜？對每個元素，檢查是否與前後相等
02/21 17:25, 18F
推
02/21 19:28, 2年前 , 19F
樓上因為題目要求
02/21 19:28, 19F
→
02/21 20:05, 2年前 , 20F
就算題目沒要求 有個執行速度更快的做法也沒不好吧
02/21 20:05, 20F
推
02/22 00:54, 2年前 , 21F
好好笑我 O(N) 的解 Beats 97.22%
02/22 00:54, 21F
→
02/22 00:55, 2年前 , 22F
原因也不難猜，大概就因為計算機結構提到的 cache miss
02/22 00:55, 22F
→
02/22 00:56, 2年前 , 23F
順向的掃過去 cache 都可以命中，二分搜跳來跳去實務上
02/22 00:56, 23F
→
02/22 00:57, 2年前 , 24F
一定比較快
02/22 00:57, 24F
推
02/22 01:30, 2年前 , 25F
還好我的二分搜還是快了
02/22 01:30, 25F
→
02/22 01:30, 2年前 , 26F
一點 O(N)會過也只是題目的N不夠大吧
02/22 01:30, 26F
推
02/22 14:27, 2年前 , 27F
N <= 1e6 時 O(N) 本來就夠快啊，除非 1e9 甚至 1e18
02/22 14:27, 27F
→
02/22 14:28, 2年前 , 28F
才會一定要 O(log N) 甚至 O(1)
02/22 14:28, 28F
推
02/22 17:42, 2年前 , 29F
M大的想法蠻有趣的 如果leetcode執行速度真的與cache
02/22 17:42, 29F
→
02/22 17:42, 2年前 , 30F
miss有關, 那這樣之後遇到的題目如果限制是10^8, 不知
02/22 17:42, 30F
→
02/22 17:42, 2年前 , 31F
道是否能用O(n)的解法解 感覺是值得嘗試
02/22 17:42, 31F
推
02/22 17:46, 2年前 , 32F
不知道能不能將cache miss量化, 不然這樣很難估實際的
02/22 17:46, 32F
→
02/22 17:46, 2年前 , 33F
複雜度
02/22 17:46, 33F
推
02/24 01:18, 2年前 , 34F
不過我自己是覺得 LeetCode 的時間本來就很不準
02/24 01:18, 34F
→
02/24 01:19, 2年前 , 35F
之前現場比賽 N=1e4 我們也是想很久亂丟 O(N^2) 結果 AC
02/24 01:19, 35F
‣ 更多 Rushia 的文章
文章代碼(AID): #1Zz43zZq (Marginalman)
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 244 之 719 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共719篇)
‣ 更多 Rushia 的文章
文章代碼(AID): #1Zz43zZq (Marginalman)