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