我們得到一個大小的網格，N * N其中每個元素A[i][j]都由這個方程計算(i j) ^ 2 (j-i) * 10^5。
我們需要以優化的方式找到第K 個最小元素。
約束：
1 <= number of test cases <= 20
1 <= N <= 5*10^4
1 <= k <= N^2
如何以有效的方式解決這個問題？
uj5u.com熱心網友回復：
您要解決的問題（在無序陣列中找到第 k 個最小元素）稱為選擇問題。有很多方法可以解決這個問題，其中一種最著名的方法是快速選擇演算法。
uj5u.com熱心網友回復：
你可以在 O(N log N) 時間內解決這個問題。請注意，這在矩陣的大小上是次線性的，即 N*N。當然，您永遠不應該實際構建矩陣。
首先，它有助于查看矩陣中的值是什么樣的：
請注意，在矩陣大小的可能范圍內，最小元素始終為 (i,j) = (N-1,0)。
最大的元素將是 (0,N-1) 或 (N-1,N-1)，具體取決于矩陣的大小。
考慮從最小到最大的線上元素。如果您選擇這些元素中的任何一個，那么您可以跟蹤輪廓以在 O(N) 時間內找到 <= 元素的數量。
此外，這一行的元素總是從最小到最大單調遞增，所以在這一行元素上進行二分查找，找到最大的，使得<=元素的數量<k。在每次測驗的時間為 O(N) 時，這總共需要 O(N log N)。
假設您發現的元素具有值 x，并且元素 <= x 的數量是 r，其中 r < k。接下來跟蹤線上下一個更高元素的輪廓，呼叫它的值 y，并列出所有值 v，使得 x < v <= y。此串列中將有 O(N) 個元素，這只需 O(N) 時間。
最后，只需使用排序或快速選擇從該串列中選擇第 (kr) 個元素。同樣，這最多需要 O(N log N) 時間。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/369677.html
上一篇：制作得分最高的平衡支架