使用 Python 查找数组游戏中获胜者的程序

假设我们有一个名为 arr 的数组，它包含唯一元素，我们还有一个值 k。现在考虑一个游戏，我们取数组的前两个元素。在每一轮中，我们将 arr[0] 与 arr[1] 进行比较，较大的值获胜并保留在位置 0，较小的值移动到数组的末尾。当某个值连续获胜 k 轮时，游戏结束。我们必须找到数组中的获胜者。

因此，如果输入类似于 arr = [1,5,6,3,4,2]，并且 k = 3，则输出将为 6，因为

  • 第 1 轮，arr = [1,5,6,3,4,2]，获胜者 5，5 的获胜次数为 1

  • 第 2 轮，arr = [5,6,3,4,2,1]，获胜者 6，6 的获胜次数为 1

  • 第 3 轮，arr = [6,3,4,2,1,5]，获胜者 6，6 的获胜次数为 2

  • 第 3 轮，arr = [6,4,2,1,5,3]，获胜者 6，6 的获胜次数为 3

所以获胜者是 6，因为它赢了三次 (k = 3)

为了解决这个问题，我们将遵循以下步骤：

  • l := arr 的大小

  • prev := arr[0]

  • count := 0

  • 对于 i 从 1 到 l - 1，执行

    • 如果 prev > arr[i]，则

      • count := count + 1

    • 否则，

      • prev := arr[i]

      • count := 1

    • 如果 count 等于 k，则

      • 返回 prev

  • 返回 prev

让我们看看以下实现以更好地理解：

示例

实时演示

def solve(arr, k):
   l = len(arr)
   prev = arr[0]
   count = 0
   for i in range(1, l):
      if prev > arr[i]:
         count+=1
      else:
         prev = arr[i]
         count = 1
      if count == k:
         return prev
   return prev
arr = [1,5,6,3,4,2]
k = 3
print(solve(arr, k))

输入

[1,5,6,3,4,2], 3

输出

6

更新于: 2021年5月29日

905 次查看

开启您的 职业生涯

通过完成课程获得认证

开始
广告