Keshawn_lu's Blog

Leetcode 5476. 找出数组游戏的赢家

数组
字数统计: 584阅读时长: 2 min
2020/08/02 Share

题目简介：

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

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

返回赢得比赛的整数。

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

示例 1：

1
2
3
4
5
输入：arr = [2,1,3,5,4,6,7], k = 2
输出：5
解释：一起看一下本场游戏每回合的情况：

因此将进行 4 回合比赛，其中 5 是赢家，因为它连胜 2 回合。

示例 2：

1
2
3
输入：arr = [3,2,1], k = 10
输出：3
解释：3 将会在前 10 个回合中连续获胜。

示例 3：

1
2
输入：arr = [1,9,8,2,3,7,6,4,5], k = 7
输出：9

示例 4：

1
2
输入：arr = [1,11,22,33,44,55,66,77,88,99], k = 1000000000
输出：99

提示：

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

思路：

首先定义一个指针j指向后续指针。

由于K过大时用正常方法会超时，所以需要单独拿出来，我们可以知道，当K >= arr.size()时，只有数组中最大的数才可能连胜这么多把，所以返回数组中最大的数即可。

每次将arr[0]与arr[j]进行比较，存在以下两种情况：

  • arr[0] < arr[j]：将arr[0]添加至数组最后，并将arr[0] = arr[j]，j向后移动一位，并将count重置为1即可。
  • arr[0] > arr[j]：此时count++，将arr[j]添加至数组最后，并将j向后移动一位即可。

当count == K时退出循环，返回arr[0]即可。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
    int getWinner(vector<int>& arr, int k) {
        
        int j = 1;
        
        int count = 0;
        
        int Max = arr[0];
        
        for(int i = 1; i < arr.size(); i++){
            
            Max = max(Max, arr[i]);
        }
        
        if(k >= arr.size())
            return Max;
        
        while(count != k){
            
            if(arr[0] < arr[j]){
                
                arr.push_back(arr[0]);
            
                arr[0] = arr[j];
                
                j++;
                count = 1;
            }
            else{
                
                count++;
                arr.push_back(arr[j]);
                
                j++;
                
            }
            
        }
        return arr[0];
    }
};
CATALOG
  1. 1. 题目简介：
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网