我在一些論壇上尋找要解決的新問題，并找到了這個：
給定一個分數陣列和一個整數 k。分數相同的玩家排名相同，玩家的排名為“得分較高的玩家人數” 1。例如，給定分數=[10,20,20,40]，對應的排名為[4, 2, 2, 1]。只有排名 <= k 的玩家才有資格進入下一輪。回傳有資格進入下一輪的玩家人數。
我想出了幾種方法來解決它，似乎我能得到的最佳時間復雜度是 O(nlog(n)) 使用以下演算法：
- 對陣列進行排序，時間復雜度為 O(nlogn)
- 然后，從 rank = 1 開始，每次傳遞到較低的分數時更新它，因此當 rank <= k 時，繼續添加符合條件的玩家數量，這具有時間復雜度 O(n)，因為我們可能最終遍歷整個陣列。
- 回傳最終計數
另一個想法是創建一些哈希表，以分數為鍵，并以玩家數量為值：
- 遍歷陣列，如果我們找到某個得分的人，則將另一個玩家添加到哈希表中該條目的值中，并且如果我們遇到的得分大于哈希表中的最小得分，則洗掉最小的分數條目，并輸入新分數（因此，到最后我們只有前 k 個分數）
- 然后將結果哈希表中的所有值加在一起（或者，至少將相關條目加在一起，因為前 k 個分數并不一定意味著這些是排名前 k 的玩家，但我們知道只需要前 k 個分數，在最大值，找到符合條件的金額）
這似乎有 O(nk) 的時間復雜度，因為我們需要遍歷整個陣列，但每次檢查我們擁有的當前 k 個分數的最小值，以確保我們只保留前 k 個分數。這通常需要比 O(nlogn) 更長的時間。
但是，我覺得必須有比我提出的方法更好的方法。有人有建議嗎？
這是原始論壇帖子：https : //leetcode.com/discuss/interview-question/1362837/goldman-sachs-new-analyst-2022-oa
uj5u.com熱心網友回復：
另一個想法如下：
- 創建一個頻率表，計算每個分數的玩家數量。這類似于您在帖子中提到的哈希表想法。鍵是唯一的分數，值是該特定分數的玩家數量。
- 使用最小堆將頻率表的鍵推送到堆。一旦堆的長度變得等于
k，對于每次新推入堆，從堆中彈出一個。這可以保證您最終k在堆中獲得最大的分數。 - 現在，回圈遍歷堆中作為 freq 表鍵的元素（不彈出），并對表中具有這些鍵的玩家數量求和。
時間復雜度方面，我們已經遍歷了初始陣列O(n)以創建頻率表，我們已經從堆中推送和彈出不同分數的數量，并且由于不同分數的數量n在最壞的情況下，這使其成為O(n * log k)操作。請注意，由于堆永遠不會超過k它log k而不是log n。最后，我們回圈了k堆中的元素，并將它們從作為k操作的頻率表中的值相加。
所以，這成為n (n * log k) k其減少了O(n * log k)在大O字條款。
uj5u.com熱心網友回復：
這是選擇問題的一個小變體：您正在尋找串列中第 k 個最小的元素，您需要輸出的答案是小于或等于第 k 個元素值的值的數量。有很多可能的解決方案，但標準的一個是Quickselect，它可以在線性O(n)時間內給出答案。讓我們看看標準選擇問題的各種越來越有效的方法，看看它們的運行時間：
- 對數字進行排序，并計算 k 個最小的： Runtime:
O(n log n)。 - 保持一個最小堆，大小以 k 為界。遍歷陣列，將每個值推入堆，并在大小達到 k 1 時彈出。運行：
O(n log k) - 最小堆化整個陣列，并彈出 k 次。有時稱為“堆選擇”。運行：
O(n k log n) - 快速選擇。通過隨機樞軸選擇，它具有
O(n)預期的運行時間和O(n^2)最壞情況的運行時間，具有良好的平均性能。使用中位數樞軸選擇，它具有O(n)最壞情況的運行時間，具有更高的常數因子。
如果您查看 C 標準庫，在演算法頭檔案中，此選擇函式稱為nth element。在實踐中，經常使用quickselect 的變體，例如introselect或 random-quickselect with heapselect fallback，它們試圖保留隨機 QuickSelect 的良好平均性能，但沒有 O(n^2) 最壞情況。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/359125.html
上一篇：這是什么意思？“nums[-1]=nums[n]=-∞”
下一篇：遍歷串列，計數重置為0