付費限定
隨機快速選擇: 陣列中第k大的元素 Kth Largest Element in Array_Leetcode #215
題目敘述
題目會給定一個陣列nums 和 給定的k值，要求我們找出陣列裡第k大的元素。
測試範例
Example 1:
Input: nums = [3,2,1,5,6,4], k = 2
Output: 5
第二大的元素為5
Example 2:
Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4
第四大的元素為4
約束條件
Constraints:
1 <= k <= nums.length <= 10^5
k 值介於1 ~ 陣列長度之間。
陣列長度介於1 ~ 10^5 之間，而且一定大於等於k。
-10^4 <= nums[i] <= 10^4
陣列內的每個元素一定介於 負一萬~正一萬 之間。
演算法 使用QuickSort的副產品，QuickSelect 快速選擇
第一直覺的寫法通常是先排序好所有陣列元素，再取出對應第k大的元素，返回答案。
從大到小排列的話，第k大的元素會恰好落在nums[k-1]這個位置上。
但是，深入思考之後，其實可以發現，我們真正要的是第k大的元素值，並不需要知道其他每一個更小或更大的值是誰。
比喻:
好比說我們拿到一副打散的牌，想知道這副牌中第3大的牌是哪一張，那麼我們每回合可以隨機選一張，把這張牌(相當於pivot)放到手牌中對應的位置。
把所有比這張牌還小的都丟到右邊(具體哪個位置無所謂，只要落在剛剛選的那張pivot還右邊即可)。
以行動支持創作者！付費即可解鎖
本篇內容共 3342 字、1
則留言，僅發佈於Leetcode精選75題 解析+統整你目前無法檢視以下內容，可能因為尚未登入，或沒有該房間的查看權限。
92會員
425內容數
由有業界實戰經驗的演算法工程師，
手把手教你建立解題的框架，
一步步寫出高效、清晰易懂的解題答案。
著重在讓讀者啟發思考、理解演算法，熟悉常見的演算法模板。
深入淺出地介紹題目背後所使用的演算法意義，融會貫通演算法與資料結構的應用。
在幾個經典的題目融入一道題目的多種解法，或者同一招解不同的題目，擴展廣度，並加深印象。
留言0
查看全部
你可能也想看
Google News 追蹤
在創作的路上真的很多人問我說
到底要怎麼做出符合自己期待
但又可以表現得很有美感的作品？🥹
這個問題真的應該是每個創作者都一直在學習的課題吧！
提問的內容越是清晰，強者、聰明人越能在短時間內做判斷、給出精準的建議，他們會對你產生「好印象」，認定你是「積極」的人，有機會、好人脈會不自覺地想引薦給你
在股票投資中，投資者往往需要利用各種技術分析工具來幫助判斷市場的走勢及最佳進出場時機。而在眾多技術分析指標中，隨機震盪指標（Stochastic Oscillator）是一個被廣泛使用的工具，它能夠幫助投資者抓住市場的轉折點，尤其在股票價格處於過度買入或過度賣出時特別有效。本文將深入探討隨機震盪指標
我們常低估極端情況出現的機率，試圖為偶然事件尋找規律。然而，接受隨機性的存在，對商業決策、人才管理和產品策略至關重要。在工作中，我們需要警惕短期表現的誤導，避免過度解讀，並以更全面、長期的視角評估情況。學會與隨機性共處，既探索規律又接受偶然，才能做出更明智的決策。
這篇內容，將會講解什麼是陣列，以及與陣列相關的知識。包括陣列的簡介、陣列的資料限制、陣列的維度、一維陣列、二維陣列。
在動物溝通的課堂上，曾經有聽到學姊分享，當經驗累積到某種程度，經過中興新村會聽到樹木在開里民大會的交談聲音，從此與植物交談這件事就一直讓我很期待，哪一天可以知道植物的心聲，想想就覺得很有趣。
上次的新竹動物園之行，還有跟河馬樂樂打招呼🙋。
天氣太熱讓樂樂只露出了眼睛跟鼻孔以上的頭部，看起來很睏倦的泡在池子裡。
※ 常用arry型態的方法：
長度：
length
查詢第N個元素：
[]
查詢元素在第N個：
indexOf( )
判斷是否為array：
isArray()
新增和刪除：
push()：新增後面的數值
unshift()：新增前面的數值
pop()：刪除後面的數值
sh
分享在網路上看到的陣列題目。通常 for...of 的 value 是陣列中的每個值，那如果我們在迭代中對陣列操作會發生什麼事？
題目來源：https://x.com/_jayphelps/status/1774640511158022335?s=20
題目敘述
題目會給定一個陣列nums 和 給定的k值，要求我們找出陣列裡第k大的元素。
題目的原文敘述
測試範例
Example 1:
Input: nums = [3,2,1,5,6,4], k = 2
Output: 5
第二大的元素為5
Example 2:
Input:
在創作的路上真的很多人問我說
到底要怎麼做出符合自己期待
但又可以表現得很有美感的作品？🥹
這個問題真的應該是每個創作者都一直在學習的課題吧！
提問的內容越是清晰，強者、聰明人越能在短時間內做判斷、給出精準的建議，他們會對你產生「好印象」，認定你是「積極」的人，有機會、好人脈會不自覺地想引薦給你
在股票投資中，投資者往往需要利用各種技術分析工具來幫助判斷市場的走勢及最佳進出場時機。而在眾多技術分析指標中，隨機震盪指標（Stochastic Oscillator）是一個被廣泛使用的工具，它能夠幫助投資者抓住市場的轉折點，尤其在股票價格處於過度買入或過度賣出時特別有效。本文將深入探討隨機震盪指標
我們常低估極端情況出現的機率，試圖為偶然事件尋找規律。然而，接受隨機性的存在，對商業決策、人才管理和產品策略至關重要。在工作中，我們需要警惕短期表現的誤導，避免過度解讀，並以更全面、長期的視角評估情況。學會與隨機性共處，既探索規律又接受偶然，才能做出更明智的決策。
這篇內容，將會講解什麼是陣列，以及與陣列相關的知識。包括陣列的簡介、陣列的資料限制、陣列的維度、一維陣列、二維陣列。
在動物溝通的課堂上，曾經有聽到學姊分享，當經驗累積到某種程度，經過中興新村會聽到樹木在開里民大會的交談聲音，從此與植物交談這件事就一直讓我很期待，哪一天可以知道植物的心聲，想想就覺得很有趣。
上次的新竹動物園之行，還有跟河馬樂樂打招呼🙋。
天氣太熱讓樂樂只露出了眼睛跟鼻孔以上的頭部，看起來很睏倦的泡在池子裡。
※ 常用arry型態的方法：
長度：
length
查詢第N個元素：
[]
查詢元素在第N個：
indexOf( )
判斷是否為array：
isArray()
新增和刪除：
push()：新增後面的數值
unshift()：新增前面的數值
pop()：刪除後面的數值
sh
分享在網路上看到的陣列題目。通常 for...of 的 value 是陣列中的每個值，那如果我們在迭代中對陣列操作會發生什麼事？
題目來源：https://x.com/_jayphelps/status/1774640511158022335?s=20
題目敘述
題目會給定一個陣列nums 和 給定的k值，要求我們找出陣列裡第k大的元素。
題目的原文敘述
測試範例
Example 1:
Input: nums = [3,2,1,5,6,4], k = 2
Output: 5
第二大的元素為5
Example 2:
Input: