[LeetCode] 1535. Find the Winner of an Array Game

Given an integer array arr of distinct integers and an integer k.

A game will be played between the first two elements of the array (i.e. arr[0] and arr[1]). In each round of the game, we compare arr[0] with arr[1], the larger integer wins and remains at position 0, and the smaller integer moves to the end of the array. The game ends when an integer wins k consecutive rounds.

Return the integer which will win the game.

It is guaranteed that there will be a winner of the game.

Example 1:
Input: arr = [2,1,3,5,4,6,7], k = 2
Output: 5
Explanation: Let’s see the rounds of the game:
Round | arr | winner | win_count
1 | [2,1,3,5,4,6,7] | 2 | 1
2 | [2,3,5,4,6,7,1] | 3 | 1
3 | [3,5,4,6,7,1,2] | 5 | 1
4 | [5,4,6,7,1,2,3] | 5 | 2
So we can see that 4 rounds will be played and 5 is the winner because it wins 2 consecutive games.

Example 2:
Input: arr = [3,2,1], k = 10
Output: 3
Explanation: 3 will win the first 10 rounds consecutively.

Constraints:
2 <= arr.length <= 105
1 <= arr[i] <= 106
arr contains distinct integers.
1 <= k <= 109

按符号重排数组。

给你一个由 不同 整数组成的整数数组 arr 和一个整数 k 。 每回合游戏都在数组的前两个元素(即 arr[0] 和 arr[1] )之间进行。比较 arr[0] 与 arr[1] 的大小,较大的整数将会取得这一回合的胜利并保留在位置 0 ,较小的整数移至数组的末尾。当一个整数赢得 k 个连续回合时,游戏结束,该整数就是比赛的 赢家 。 返回赢得比赛的整数。 题目数据 保证 游戏存在赢家。

思路

思路是模拟。这里有两个 corner case 需要处理,如果如果回合数 k == 1,那么返回的就是前两个数字里较大的那个。另一个 case 是如果遍历一次之后,整个数组中未出现赢得 k 次游戏的数字,那么全局最大的数字是赢家,因为这个数字有可能排在 input 数组很后面的位置导致 index 比他大的数字的个数不足 k 个。

一般的情况是,我们比较了头两个元素之后,从第三个元素开始,就只和第一个元素(赢家)比较并记录连续赢得比赛的回合数,如果有任何一个数字连续赢得比赛的回合数 == k 则返回这个数字。

复杂度

时间O(n)
空间O(n)

代码

Java实现

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
class Solution {
public int getWinner(int[] arr, int k) {
int first = arr[0];
int second = arr[1];
// 前两个数字的较大者
int max = Math.max(first, second);
// corner case
if (k == 1) {
return max;
}

// normal case
int count = 1;
for (int i = 2; i < arr.length; i++) {
int bigger = Math.max(max, arr[i]);
// 如果比较之后还是max大,则count++
// 反之max要更新为当前更大的数字,count重置为1
if (max == bigger) {
count++;
} else {
max = bigger;
count = 1;
}
if (count == k) {
return max;
}
max = Math.max(max, bigger);
}
return max;
}
}

[LeetCode] 1535. Find the Winner of an Array Game
https://shurui91.github.io/posts/1740553697.html
Author
Aaron Liu
Posted on
November 5, 2023
Licensed under