Find the Losers of the Circular Game 找出轉圈游戲輸家

問題描述：

n 個朋友在玩游戲。這些朋友坐成一個圈，按 順時針方向 從 1 到 n 編號。從第 i 個朋友的位置開始順時針移動 1 步會到達第 (i + 1) 個朋友的位置（1 <= i < n），而從第 n 個朋友的位置開始順時針移動 1 步會回到第 1 個朋友的位置。

游戲規則如下：

第 1 個朋友接球。

• 接著，第 1 個朋友將球傳給距離他順時針方向 k 步的朋友。
• 然后，接球的朋友應該把球傳給距離他順時針方向 2 * k 步的朋友。
• 接著，接球的朋友應該把球傳給距離他順時針方向 3 * k 步的朋友，以此類推。

換句話說，在第 i 輪中持有球的那位朋友需要將球傳遞給距離他順時針方向 i * k 步的朋友。

當某個朋友第 2 次接到球時，游戲結束。

在整場游戲中沒有接到過球的朋友是 輸家 。

給你參與游戲的朋友數量 n 和一個整數 k ，請按升序排列返回包含所有輸家編號的數組 answer 作為答案。

$1<=k<=n<=50$

分析

這個問題是一次周賽的Q1。

這樣的問題很討厭，因為它太簡單了，直接模擬就可以了，但是大部分的人潛意識中，會被導向約瑟夫環。

沒錯，當時這個問題花了近半小時，雖然AC，但是代碼太挫了。

可能是周賽的影響，今天的每日就很流暢。這個模擬需要注意的是它的No.是從1開始到n。而且是一個環，所以取模是必然的。

這時候就需要一個長度n的標識數組，來記錄是否訪問過。
所以編號為$i$的人，就會處于數組$i?1$的位置上。
那么下一個可以被訪問的人，$j=(i+r?k)$,$i$和$j$都是索引。
在不停的訪問中，一定會終止，即某個位置第二次被訪問到。
此時把所有未被標記的位置從小到大的記錄到結果中.

目前這個問題似乎，沒有純數學的思路，只能模擬。

代碼

模擬

public int[] circularGameLosers(int n, int k) {boolean[] mark = new boolean[n];int r = 0;//圈數for(int i = 0;!mark[i];i =(i+r*k)%n){mark[i] = true;r++;}int[] ans = new int[n-r];for(int i=0,j=0;i<n;i++){if(!mark[i]) ans[j++]= i+1;}return ans;}

時間復雜度$O(N)$

空間復雜度$O(N)$

Tag

Array

Hash