LeetCode390. 消除游戲題解（Medium）
- 題目內容
- 題解
- 等引數列模擬
- 復雜度
等引數列相關知識
擴展：等比數列相關知識
題目內容
390. 消除游戲
串列 arr 由在范圍 [1, n] 中的所有整陣列成，并按嚴格遞增排序，請你對 arr 應用下述演算法：
從左到右，洗掉第一個數字，然后每隔一個數字洗掉一個，直到到達串列末尾，
重復上面的步驟，但這次是從右到左，也就是，洗掉最右側的數字，然后剩下的數字每隔一個洗掉一個，
不斷重復這兩步，從左到右和從右到左交替進行，直到只剩下一個數字，
給你整數 n ，回傳 arr 最后剩下的數字，
題解
等引數列模擬
依照題意，我們每次都將整數串列進行間隔洗掉，因此每次洗掉后剩余的整數串列都是等引數列，
初始時尚未洗掉任何元素，
如果是偶數，則從左向右洗掉，
如果元素數目為奇數，則兩端的元素都會被洗掉，
如果元素數目?為偶數，則首端元素會被洗掉，末端元素不會被洗掉，
如果是奇數，則從右向左洗掉，
如果元素數目為奇數，則兩端的元素都會被洗掉，
如果元素數目為偶數，則首端元素不會被洗掉，末端元素會被洗掉，
當等引數列只剩一個元素時，回傳首元素即可，
class Solution {
public:
int lastRemaining(int n) {
int a1 = 1, an = n;
int k = 0, cnt = n, step = 1;
while (cnt > 1) {
if (k % 2 == 0) { // 正向
a1 = a1 + step;
an = (cnt % 2 == 0) ? an : an - step;
} else { // 反向
a1 = (cnt % 2 == 0) ? a1 : a1 + step;
an = an - step;
}
k++;
cnt = cnt >> 1;
step = step << 1;
}
return a1;
}
};
作者：LeetCode-Solution
鏈接：https://leetcode-cn.com/problems/elimination-game/solution/xiao-chu-you-xi-by-leetcode-solution-ydpb/
來源：力扣（LeetCode）
復雜度
時間復雜度：O(logn)，其中 n 為初始整數串列的元素數目，每次洗掉都會將元素數目減半，所以時間復雜度為O(logn)，
空間復雜度：O(1)，只需要使用常數的額外空間，
注：其實不用實際真的移除，記錄一下每次剩下的最大最小值以及本輪移除的間隔就好了
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/401481.html
標籤：其他
下一篇：390. 消除游戲