1535. Find the Winner of an Array Game

leetcode medium

#array#csharp#leetcode#math#medium#queue#search

Task

Дан целочисленный массив

arr

из различных целых чисел и целое число

Игра будет проводиться между первыми двумя элементами массива (т.е.

arr[0]

arr[1]

). В каждом раунде игры мы сравниваем

arr[0]

arr[1]

, большее число побеждает и остается на позиции 0, а меньшее число перемещается в конец массива. Игра заканчивается, когда одно число выигрывает

подряд раундов.

Верните число, которое выиграет игру.

Гарантируется, что у игры будет победитель.

Пример:

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.

C# solution

matched/original

public class Solution {
    public int GetWinner(int[] arr, int k) {
        int maxElement = arr[0];
        Queue<int> queue = new Queue<int>();
        for (int i = 1; i < arr.Length; i++) {
            maxElement = Math.Max(maxElement, arr[i]);
            queue.Enqueue(arr[i]);
        }
        
        int curr = arr[0];
        int winstreak = 0;
        
        while (queue.Count > 0) {
            int opponent = queue.Dequeue();
            
            if (curr > opponent) {
                queue.Enqueue(opponent);
                winstreak++;
            } else {
                queue.Enqueue(curr);
                curr = opponent;
                winstreak = 1;
            }
            
            if (winstreak == k || curr == maxElement) {
                return curr;
            }
        }
        
        return -1;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int GetWinner(vector<int>& arr, int k) {
        int maxElement = arr[0];
        queue<int> queue = new queue<int>();
        for (int i = 1; i < arr.size(); i++) {
            maxElement = max(maxElement, arr[i]);
            queue.Enqueue(arr[i]);
        }
        
        int curr = arr[0];
        int winstreak = 0;
        
        while (queue.size() > 0) {
            int opponent = queue.Dequeue();
            
            if (curr > opponent) {
                queue.Enqueue(opponent);
                winstreak++;
            } else {
                queue.Enqueue(curr);
                curr = opponent;
                winstreak = 1;
            }
            
            if (winstreak == k || curr == maxElement) {
                return curr;
            }
        }
        
        return -1;
    }
}

Java solution

matched/original

class Solution {
    public int getWinner(int[] arr, int k) {
        int maxElement = arr[0];
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i < arr.length; i++) {
            maxElement = Math.max(maxElement, arr[i]);
            queue.offer(arr[i]);
        }
        
        int curr = arr[0];
        int winstreak = 0;
        
        while (!queue.isEmpty()) {
            int opponent = queue.poll();
            
            if (curr > opponent) {
                queue.offer(opponent);
                winstreak++;
            } else {
                queue.offer(curr);
                curr = opponent;
                winstreak = 1;
            }
            
            if (winstreak == k || curr == maxElement) {
                return curr;
            }
        }
        
        return -1;
    }
}

JavaScript solution

matched/original

class Solution {
    getWinner(arr, k) {
        let maxElement = arr[0];
        let queue = arr.slice(1);
        
        for (let element of arr.slice(1)) {
            maxElement = Math.max(maxElement, element);
        }
        
        let curr = arr[0];
        let winstreak = 0;
        
        while (queue.length > 0) {
            let opponent = queue.shift();
            
            if (curr > opponent) {
                queue.push(opponent);
                winstreak++;
            } else {
                queue.push(curr);
                curr = opponent;
                winstreak = 1;
            }
            
            if (winstreak === k || curr === maxElement) {
                return curr;
            }
        }
        
        return -1;
    }
}

Python solution

matched/original

from collections import deque

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        maxElement = arr[0]
        queue = deque(arr[1:])
        
        for element in arr[1:]:
            maxElement = max(maxElement, element)
        
        curr = arr[0]
        winstreak = 0
        
        while queue:
            opponent = queue.popleft()
            
            if curr > opponent:
                queue.append(opponent)
                winstreak += 1
            else:
                queue.append(curr)
                curr = opponent
                winstreak = 1
            
            if winstreak == k or curr == maxElement:
                return curr
        
        return -1

Go solution

matched/original

public class Solution {
    public int GetWinner(int[] arr, int k) {
        int maxElement = arr[0];
        Queue<int> queue = new Queue<int>();
        for (int i = 1; i < arr.Length; i++) {
            maxElement = Math.Max(maxElement, arr[i]);
            queue.Enqueue(arr[i]);
        }
        
        int curr = arr[0];
        int winstreak = 0;
        
        while (queue.Count > 0) {
            int opponent = queue.Dequeue();
            
            if (curr > opponent) {
                queue.Enqueue(opponent);
                winstreak++;
            } else {
                queue.Enqueue(curr);
                curr = opponent;
                winstreak = 1;
            }
            
            if (winstreak == k || curr == maxElement) {
                return curr;
            }
        }
        
        return -1;
    }
}

Explanation

Algorithm

1⃣Инициализируйте maxElement как максимальный элемент в arr, queue как очередь с элементами массива, кроме первого, curr = arr[0] и winstreak = 0.

2⃣Пока очередь не пуста (или используйте бесконечный цикл), извлеките opponent из начала очереди. Если curr > opponent, добавьте opponent в конец очереди и увеличьте winstreak на 1. В противном случае добавьте curr в конец очереди, установите curr = opponent и winstreak = 1.

3⃣Если winstreak = k или curr = maxElement, верните curr. Код никогда не должен достигать этой точки, так как гарантированно есть победитель. Верните любое значение.

😎