Сложность: medium
Дан целочисленный массив
arr из различных целых чисел и целое число k.Игра будет проводиться между первыми двумя элементами массива (т.е.
arr[0] и arr[1]). В каждом раунде игры мы сравниваем arr[0] с arr[1], большее число побеждает и остается на позиции 0, а меньшее число перемещается в конец массива. Игра заканчивается, когда одно число выигрывает k подряд раундов.Верните число, которое выиграет игру.
Гарантируется, что у игры будет победитель.
Пример:
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.
👨💻 Алгоритм:
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. Код никогда не должен достигать этой точки, так как гарантированно есть победитель. Верните любое значение.
😎 Решение:
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;
}
}Ставь 👍 и забирай 📚 Базу знаний