找出数组游戏的赢家

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 回合。

示例 2：

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

示例 3：

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

示例 4：

输入：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

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int getWinner(vector<int>& arr, int k) { } };

python3 解法, 执行用时: 52 ms, 内存消耗: 27.2 MB, 提交时间: 2024-05-19 08:51:34

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        mx = arr[0]
        win = -1  # 对于 arr[0] 来说，需要连续 k+1 个回合都是最大值
        for x in arr:
            if x > mx:  # 新的最大值
                mx = x
                win = 0
            win += 1  # 获胜回合 +1
            if win == k:
                break
        return mx

rust 解法, 执行用时: 4 ms, 内存消耗: 3.5 MB, 提交时间: 2024-05-19 08:51:16

impl Solution {
    pub fn get_winner(arr: Vec<i32>, k: i32) -> i32 {
        let mut mx = arr[0];
        let mut win = -1; // 对于 arr[0] 来说，需要连续 k+1 个回合都是最大值
        for &x in &arr {
            if x > mx { // 新的最大值
                mx = x;
                win = 0;
            }
            win += 1; // 获胜回合 +1
            if win == k {
                break;
            }
        }
        mx
    }
}

javascript 解法, 执行用时: 78 ms, 内存消耗: 58.9 MB, 提交时间: 2024-05-19 08:51:02

/**
 * @param {number[]} arr
 * @param {number} k
 * @return {number}
 */
var getWinner = function(arr, k) {
    let mx = arr[0];
    let win = 0;
    for (let i = 1; i < arr.length && win < k; i++) {
        if (arr[i] > mx) { // 新的最大值
            mx = arr[i];
            win = 0;
        }
        win++; // 获胜回合 +1
    }
    return mx;
};

golang 解法, 执行用时: 65 ms, 内存消耗: 8.5 MB, 提交时间: 2024-05-19 08:50:49

func getWinner(arr []int, k int) int {
    mx := arr[0]
    win := 0
    for i := 1; i < len(arr) && win < k; i++ {
        if arr[i] > mx { // 新的最大值
            mx = arr[i]
            win = 0
        }
        win++ // 获胜回合 +1
    }
    return mx
}

cpp 解法, 执行用时: 76 ms, 内存消耗: 64 MB, 提交时间: 2024-05-19 08:50:34

class Solution {
public:
    int getWinner(vector<int>& arr, int k) {
        int mx = arr[0], win = 0;
        for (int i = 1; i < arr.size() && win < k; i++) {
            if (arr[i] > mx) { // 新的最大值
                mx = arr[i];
                win = 0;
            }
            win++; // 获胜回合 +1
        }
        return mx;
    }
};

java 解法, 执行用时: 0 ms, 内存消耗: 58.3 MB, 提交时间: 2024-05-19 08:50:21

class Solution {
    public int getWinner(int[] arr, int k) {
        int mx = arr[0];
        int win = 0;
        for (int i = 1; i < arr.length && win < k; i++) {
            if (arr[i] > mx) { // 新的最大值
                mx = arr[i];
                win = 0;
            }
            win++; // 获胜回合 +1
        }
        return mx;
    }
}

python3 解法, 执行用时: 88 ms, 内存消耗: 22.9 MB, 提交时间: 2020-08-16 20:43:02

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        a, n = arr[0], 0
        for i in arr[1:]:
            if i > a:
                a, n = i, 1
            else:
                n += 1
            if n == k:
                return a
        return a

上一题

下一题

详情