1535. Find the Winner of an Array Game
給你一個陣列 arr 表示比賽順序
k 表示勝利次數
每次比賽的時候 arr[0] 會跟 arr[1] 比
勝利的數字會跑到 arr[0] 而輸的會跑到陣列尾端
遊戲會進行到有人連續勝利 k 次後結束
例題:
1.
Input: arr = [2,1,3,5,4,6,7], k = 2
Output: 5
回合 | 陣列 | 勝者 | 勝利次數
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
5 連續勝利兩次 比賽結束
2.
Input: arr = [3,2,1], k = 10
Output: 3
First think:
範例題目就展示了這一提的一個特性：
陣列中的最大值不一定是贏家
可能還沒比完就找到贏家了
以一開始覺得陣列順序可能會亂掉
如果會比到第二輪的話
需要對陣列做操作才能知道正確的比賽順序
Approach:
仔細思考就能發現
如果第一輪比完的話
當下的衛冕者就是陣列最大值
所以接下來不管怎麼比結果都不會變
這樣的話我們就不需要考慮第二輪的狀況
也就不需要進行陣列操作
單純記錄勝利次數就好了
TS code:
function getWinner (arr: number[], k: number): number {
let winner = arr[0]
let winCount = 0
const WinnerWin = () => {
winCount++
}
const WinnerLost = (newWinner: number) => {
winner = newWinner
winCount = 1
}
for (let i = 1; i < arr.length; i++) {
if (winner > arr[i]) {
WinnerWin()
} else {
WinnerLost(arr[i])
}
if (winCount === k) return winner
}
return winner
}