526互联

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

发布时间 2023-11-05 13:55:46作者: CNoodle

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 需要处理，如果 input 数组只有两个数字，那么赢家就是这两个值中间较大的那一个。另一个 case 是如果遍历一次之后，整个数组中未出现赢得 k 次游戏的数字，那么全局最大的数字是赢家，因为这个数字有可能排在 input 数组很后面的位置导致 index 比他大的数字的个数不足 k 个。

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

时间O(n)
空间O(n)
Java实现

class Solution {
    public int getWinner(int[] arr, int k) {
        int prev = Math.max(arr[0], arr[1]);
        int count = 1;
        int max = prev;
        // corner case
        if (k == 1) {
            return prev;
        }

        // normal case
        for (int i = 2; i < arr.length; i++) {
            int cur = arr[i];
            if (prev > cur) {
                count++;
            } else {
                prev = cur;
                count = 1;
            }
            if (count == k) {
                return prev;
            }
            max = Math.max(max, arr[i]);
        }
        return max;
    }
}