推 SecondRun: 是不是大於陣列長-1就可以直接傳max了 11/05 14:32
→ SecondRun: 大於等於陣列長-1 11/05 14:32
→ Rushia: 是沒錯 這樣寫是只是比較懶 反正時間複雜度沒怎麼差 11/05 14:38
※ 引述《ZooseWu (動物園 公告)》之銘言：
: 1535. Find the Winner of an Array Game
: 給你一個陣列 arr 表示比賽順序
: k 表示勝利次數
: 每次比賽的時候 arr[0] 會跟 arr[1] 比
: 勝利的數字會跑到 arr[0] 而輸的會跑到陣列尾端
: 遊戲會進行到有人連續勝利 k 次後結束
https://leetcode.com/problems/find-the-winner-of-an-array-game/description
思路：
1.如果 k 大於等於陣列長，代表需要贏過所有人，所以直接返回最大元素。
2.否則按照題目的要求，輸的放到最後一個，贏的放第一個，因為要把小元素移到後面
並把後面的元素往前補，這個操作對陣列來說成本很高，所以我們可以改用雙指針，
指針 i 指向第一個元素，指針 j 不斷的往右並取 mod 當作比較的元素。
（題目保證有解）
JavaCode：
------------------------------------------------
class Solution {
public int getWinner(int[] arr, int k) {
if (k >= arr.length) {
return getMax(arr);
}
int count = 0;
int i = 0; // winner
int j = 0;
while (count != k) {
j = (j + 1) % arr.length;
if (i == j) continue;
if (arr[i] > arr[j]) {
count++;
} else {
i = j;
count = 1;
}
}
return arr[i];
}
int getMax(int[] arr) {
int max = arr[0];
for (int n : arr) {
max = Math.max(max, n);
}
return max;
}
}
------------------------------------------------
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.73.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1699164863.A.BF3.html