[M模拟] lc1823. 找出遊戲的獲勝者(模拟+約瑟夫環+周賽236_2)

文章目錄

• • 1. 題目來源
  • 2. 題目解析

1. 題目來源

連結：lc1823. 找出遊戲的獲勝者

相關題目：[劍指-Offer] 62. 圓圈中最後剩下的數字(數學、環形連結清單、約瑟夫環、巧妙解法)

2. 題目解析

約瑟夫環問題。一般拿環形連結清單模拟可做，也是在資料結構一章中環形連結清單的經典應用，在競賽中一時沒想起來，直接數組暴力模拟也過了，資料範圍太小了。但是寫了一個很醜的代碼，卻好在 1a 了。

數組模拟思路：

• 一個大小為

  n

  的數組，用 0 1 标記該位置是否有效。總共循環

  n - 1

  次，每次循環周遊

  k

  個有效的位置，将其标記，代表其被槍斃。然後再從該位置尋找到下一個有效的位置将其作為起點即可。

遞歸思路：

• 記

  f(n, k)

  為

  n

  個人，跳

  k

  步的最後勝利者的編号，在此要求是從下标 0 開始的，即它的下标是

  0,1,2,3,...,n-1

  。
• 考慮

  f(n-1, k)

  此時下标應該從

  k

  開始，可寫作

  k, k+1, k+2,...,0,1,2,...,k-2

  ，總共

  n-1

  個人，現在從下标

  k

  開始報數。
• 但是

  f(n-1,k)

  的定義是

  n-1

  個人從下标 0 開始報數最後的幸存者，這兩者并不等價，即

  f(n,k)!=f(n-1,k)

  。
• 那麼

  f(n-1,k)

  是從下标

  0,1,2,3,...,n-2

  開始構成的一個約瑟夫環，環内

  n-1

  個點，我們可以将這個環轉

  k

  下，讓 0 對應到

  k

  ，後面的均将一一對應。
• 故考慮做下标映射，即：将

  k, k+1, k+2,...,n-1,0,1,2,...,k-2

  ，總共

  n-1

  個人，映射為

  0,1,2,3,...,n-2

  ，0 和

  k

  一一對應，1 和

  k+1

  一一對應，

  k-2

  和

  n-2

  一一對應。
• 此時

  f(n-1,k)

  就是下标

  0,1,2,3,...,n-2

  得到的勝利者的編号了，但是我們需要将這個結果映射到

  k, k+1, k+2,...,n-1,0,1,2,...,k-2

  中，觀察可以發現每一項就是多加了個

  k

  ，為了保證下标是在合法範圍内，再

  %n

  ，将下标再映射到

  [0,n-1]

  。其實在此有個疑問就是為啥不是映射到

  %(n-1)

  中呢，畢竟隻有

  n-1

  個數啊，數的範圍就是

  [0,n-2]

  啊。但是實際上，這裡的映射

  %n

  并不是針對

  0,1,2,...,n-2

  的，而是針對

  f(n,k)

  這

  n

  個數作的映射，同理

  f(n-1,k)

  就得

  %(n-1)

  ，這個模數是随着第一個參數遞減的。

• f(n-1,k)

  做完下标映射之後，就是以下标為

  k

  開始的

  n-1

  個人中的最後勝利者，這就和

  f(n,k)

  的勝利者完全等價了。故

  f(n,k)= (f(n-1,k)+k)%n

  ，這就是一個非常簡潔的遞推式了，可以遞推、遞歸實作。
• 邊界情況就是當

  n==1

  的時候，傳回下标 0 即可，即自己直接勝出。
• 最後注意題目要求是從下标 1 開始，結果需要加 1。

要注意一點，這個

%n

随着

f(n-1,k)

的不斷遞減，模數也會不斷減少！這點在遞歸改疊代的過程中相當重要！

• 時間複雜度： O ( n ) O(n) O(n)。
• 空間複雜度： O ( 1 ) O(1) O(1)

代碼：

自己寫的繁瑣的模拟代碼

class Solution {
public:
    int findTheWinner(int n, int k) {
        vector<int> q(n);
        int cnt = n, index = 0;
        for (int i = 1; i < n; i ++ ) {
            for(int i = index, cnt = 0; cnt < k; i ++ ) {
                if (i == n) i = 0;
                if (q[i] == 0) cnt ++;
                index = i;
            }
            
            q[index] = 1;
            for (int i = index; i <= n; i ++ ) {
                if (i == n) {
                    i = 0;
                }
                if (q[i] == 0) {
                    index = i;
                    break;
                }
            }
        }
        for (int i = 0; i < n; i ++ ) 
            if (q[i] == 0)
                return i + 1;
        return 0;
    }
};
           

大佬簡潔的模拟寫法：

class Solution
{
public:
    int findTheWinner(int n, int k) 
	{
		vector<int> a(n);
		for (int i = 0; i < n; ++i) {		// 0~n-1 代表序号，1~n 對應它的數值
			a[i] = i + 1;					// 真是及其巧妙的資料組織！
		}
		int at = 0;
		while (a.size() > 1) {
			at = (at + k - 1) % a.size();	// 找到下标，取模防止越界處理
			a.erase(a.begin() + at);
		}
		return a[0];
	}
};
           

約瑟夫經典遞歸：

// 需要最後下标 +1，不友善寫一行
class Solution {
public:
    int f(int n, int k) {
        if (n == 1) return 0;
        return (f(n - 1, k) + k) % n;
    }
    int findTheWinner(int n, int k) {
        return f(n, k) + 1;
    }
};
           

約瑟夫疊代寫法：

class Solution {
public:
    int findTheWinner(int n, int k) {
        int ans = 0;   // i=1 的情況，ans=0，循環也可以從i=1開始，因為 %1=0，ans無變化
        for (int i = 2; i <= n; i ++ ) ans = (ans + k) % i;
        return ans + 1;
    }
};