Python 列表中查詢第 k 大元素的程式

假設我們有三個值 n、total 和 k。現在考慮一個大小為 n 的列表，其總和與 total 相同，並且任何兩個連續元素之間的絕對差最多為 1。我們必須找到此列表中索引 k 處的最大值。

因此，如果輸入類似於 n = 5 total = 15 k = 3，則輸出將為 4，因為一個可能的列表類似於 [3,2,3,4,3]，在索引 3 處找到的最大元素為 4。

為了解決這個問題，我們將遵循以下步驟：

• x := 0
• 重複執行以下操作：
  • a := k + 1
  • s := (x + x - a + 1) * floor(a/2)
  • a := n - k
  • s := s + (x + x - a + 1) * floor(a/2)
  • s := s - x
  • 如果 s > total，則
    • 退出迴圈
  • x := x + 1
• 返回 x - 1

示例

讓我們看看下面的實現來更好地理解：

def solve(n, total, k):
   x = 0
   while 1:
      a = k + 1
      s = (x + x - a + 1) * a // 2
      a = n - k
      s += (x + x - a + 1) * a // 2
      s -= x
      if s > total:
         break
      x += 1
   return x - 1

n = 5
total = 15
k = 3
print(solve(n, total, k))

輸入

5, 15, 3

輸出

4

Arnab Chakraborty

更新於：2021年10月19日

瀏覽量 165

開啟您的職業生涯

透過完成課程獲得認證

開始學習