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

更新于：2021年10月19日

浏览量 165

开启您的职业生涯

通过完成课程获得认证

开始学习
广告