1535. 找出数组游戏的赢家

题目

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

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

返回赢得比赛的整数。

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

示例 1：

输入：arr = [2,1,3,5,4,6,7], k = 2 输出：5 解释：一起看一下本场游戏每回合的情况： 因此将进行 4 回合比赛，其中 5 是赢家，因为它连胜 2 回合。

思路

这题很明显不能按部就班的做，不然每次都要做数组的复制操作，肯定会超时，但是一开始我还是用了笨方法做了，主要像试一试java的数组拷贝函数 代码如下：

public static int getWinner(int[] arr, int k) { int win = arr[0]; int num = 0; int n = arr.length - 1; int i = 0; //这里需要注意的是，当遍历完数组一遍之后，数组中的最大值已经移到了第一个位置，如果num还是小于k //那么直接返回数组的最大值就行了 while (num < k && i <= n) { i++; if (arr[0] > arr[1]) { num++; win = arr[0]; if (i <= n) { int tmp = arr[1]; System.arraycopy(arr, 2, arr, 1, n - 1); arr[n] = tmp; } } else { num = 1; win = arr[1]; if (i <= n) { int tmp = arr[0]; System.arraycopy(arr, 1, arr, 0, n); arr[n] = tmp; } } } return win; }

优化思路

直接上代码

public static int getWinner(int[] arr, int k) { //初始化win为arr[0] int win = arr[0]; int num = 0; //初始化胜利次数 int n = arr.length; for(int i=1;i<n;i++){ if(win>arr[i]){ num++; if(num==k){ return win; } }else{ win = arr[i]; //win易主了，那么num更新为1 num = 1; if(num==k){ return win; } } } return win; }

参考：

https://leetcode-cn.com/problems/find-the-winner-of-an-array-game/solution/zhao-chu-shu-zu-you-xi-de-ying-jia-by-leetcode-sol/