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. 代码如下: