LeetCode之找出数组游戏的赢家（五千四百七十六）

目录

题目

解题

方法一、动态规划

题目

（原题链接：https://leetcode-cn.com/problems/find-the-winner-of-an-array-game/）

给你一个由 不同 整数组成的整数数组 arr 和一个整数 k 。

每回合游戏都在数组的前两个元素（即 arr[0] 和 arr[1] ）之间进行。比较 arr[0] 与 arr[1] 的大小，较大的整数将会取得这一回合的胜利并保留在位置 0 ，较小的整数移至数组的末尾。当一个整数赢得 k 个连续回合时，游戏结束，该整数就是比赛的 赢家 。

返回赢得比赛的整数。

题目数据 保证 游戏存在赢家。

示例 1：

提示：

• 2 <= arr.length <= 10^5
• 1 <= arr[i] <= 10^6
• arr 所含的整数 各不相同 。
• 1 <= k <= 10^9

解题

方法一、动态规划

分析：通过理解题意，可以将比较过程类比成冒泡过程，我们在冒泡过程需要注意是否为连续胜出的情况。

代码：（C++）

      class Solution {
      public:
      int getWinner(vector<int>& arr, int k) {
      int i = 0;
      int t = 0;  // t记录连胜次数
      while(t < k && i < arr.size() - 1){
      if (arr[i] > arr[i+1]) {
       arr[i+1] = arr[i];
       ++t; // 连续胜出+1
       } else {
       t = 1; // 不连续胜出重置1
       }
       ++i;
       }
      return arr[i];
       }
      };
  
 

时间复杂度：O（n*m*p）。

空间复杂度：O（1）。

执行结果：

文章来源: liuzhen.blog.csdn.net，作者：Data-Mining，版权归原作者所有，如需转载，请联系作者。

原文链接：liuzhen.blog.csdn.net/article/details/107752240