找出陣列遊戲的贏家 Find the Winner of an Array Game Leetcode_1535

這題的題目在這裡:

題目敘述

題目會給們一個陣列，還有一個k值。

接著進行比大小的遊戲，規則如下:

每次取陣列前兩個元素值比大小，比較小的會被重新安排到陣列最後方，陣列前兩個元素值比大小，同樣的，比較小的會被重新安排到陣列最後方。依此類推，反覆進行比大小的遊戲。

請問第一個能連贏k回合的是哪一個數字?

測試範例

Example 1:

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.

Example 2:

Input: arr = [3,2,1], k = 10
Output: 3
Explanation: 3 will win the first 10 rounds consecutively.

約束條件

Constraints:

• 2 <= arr.length <= 105
• 1 <= arr[i] <= 106
• arr contains distinct integers.
• 1 <= k <= 109

演算法

第一時間可能會想要找一個queue或是deque等等FIFO相關的資料結構來進行遊戲模擬。

但是，其實仔細觀察遊行進行規律，可以發現，每次比較小的數字都會被重新安排在最後面。而且，比較小的數字不會是最終的贏家。

因此，我們可以做一個線性掃描，從左邊掃描到最右邊，找出連贏K回合的贏家數字。

一開始初始化，假設贏家是第一個數字。

接著，和後續的數字進行兩兩比大小的遊戲，統計連贏的回合數，最終連贏K回合的就是這個遊戲的贏家。

程式碼

class Solution:
　def getWinner(self, arr: List[int], k: int) -> int:
　　
　　# Simple cases
　　if k >= len(arr):
　　　return max(arr)

　　# General cases
　　winnwer = arr[0]
　　win_count = 0

　　# Scan possible competitor from left to right
　　for i in range(1, len(arr) ):

　　　
　　　if arr[i] > winnwer:
　　　　# Competitor wins, update new winner
　　　　winnwer = arr[i]
　　　　win_count = 1
　　　else:
　　　　# Competitor loses
　　　　win_count += 1

　　　if win_count == k:
　　　　break
　　
　　return winnwer

複雜度分析

時間複雜度: O( n)
一次線性掃描，掃描長度和陣列長度一樣長O(n)。

空間複雜度: O(1)
使用到的變數都是固定尺寸的臨時變數，皆為常數級別O(1)。

關鍵知識點

觀察遊行進行規律，可以發現，每次比較小的數字都會被重新安排在最後面。而且，比較小的數字不會是最終的贏家。

因此，我們可以做一個線性掃描，從左邊掃描到最右邊，找出連贏K回合的贏家數字。

Reference:

[1] Python O(n) by linear scan on possible competitor [w/ Comment] - Find the Winner of an Array Game - LeetCode