首页 > 代码库 > IT公司100题-18-圆圈中最后剩下的数字

IT公司100题-18-圆圈中最后剩下的数字

2024-07-16 23:07:15   223人阅读

问题描述：
n个数字(下标为0, 1, …, n-1)形成一个圆圈，从数字0开始，每次从这个圆圈中删除第m个数字(当前数字从1开始计数)。当一个数字被删除后，从被删除数字的下一个数字开始计数，继续删除第m个数字。求这个圆圈中剩下的最后一个数字。
 
分析：
这是有名的约瑟夫环问题。
最直接的方法：
使用链表来模拟整个删除过程。因为需要n个链表节点，所以空间复杂度为O(n)。每删除一个节点，都需要m次运算，所以时间复杂度为O(mn)。

实现代码如下所示：

 1 // 18_1.cc 2 #include <iostream> 3 #include <list> 4 using namespace std; 5  6 int josephus(size_t n, size_t m) { 7     if (n < 1 || m < 1) 8         return -1; 9     else if (n == 1)10         return 0;11 12     list<int> jos;13     for(size_t i = 0; i < n; i++)14         jos.push_back(i);15 16     list<int>::iterator it = jos.begin();17     while(jos.size() > 1) {18         for(size_t i = 1; i <= m; i++) {19             it++;20             if(it == jos.end())  // 模拟环形21                 it = jos.begin();22         }23 24         list<int>::iterator next = it;25 26         if (it == jos.begin())27             it = jos.end();28         it--;29         jos.erase(it);30         it = next;31     }32 33     return *it;34 }35 36 int main() {37     size_t n = 10;38     size_t m = 2;39     cout << "The last one is: " << josephus(n, m) << endl;40     return 0;41 }
从数学角度推导递推公式：
(1) 最开始n个数字为:0, 1, 2, … , n-1，该序列最后剩下的数字，是关于n和m的函数，记为f(n,m)。
(2) 第一次删除的节点为：(m-1)%n，这里记为k=(m-1)%n。
(3) 删除k之后，剩下的数字序列为k+1, k+2, …, n-1, 0, 1, …, k-1。该序列最后剩下的数字，是也是关于n-1和m的函数，只是规则不通过，记为f’(n-1, m)。
(4) (1)中最后剩下的数字和(3)中最后剩下的数字是相同的，所以f(n, m) = f’(n-1, m)。
(5) 对剩下的数字序列，做一个映射p(x) = (x-(k+1))%n，映射之前数字为x，映射之后为(x-(k+1))%n，如下所示：
k+1    ->    0
k+2    ->    1
…
n-1     ->    n-k-2
0        ->    n-k-1
…
k-1     ->    n-2
在这里，很容易知道p(x)函数的逆函数为：p-1(x) = (x+(k+1))%n
(5) 映射完之后的序列，也是从0开始的，所以可以继续使用f函数来标识，记为f(n-1, m)。
f(n-1, m) = p[f‘(n-1, m)] 推出 f’(n-1, m) = p-1[f(n-1, m)] = (f(n-1, m) + (k+1))%n
将k=(m-1)%n代入得：f’(n-1, m) = (f(n-1, m) + m)%n
即f(n, m) = (f(n-1, m) + m)%n
ok, 得到递推公式：
f(n, m) = 0, if n==1
f(n, m) = (f(n-1, m) + m)%n if n> 1
使用上述递推公式，时间复杂度为O(n)，空间复杂度为O(1)。

实现代码如下所示：

 1 // 18_2.cc 2 #include <iostream> 3 using namespace std; 4  5 int josephus(size_t n, size_t m) { 6     if (n < 1 || m < 1) 7         return -1; 8  9     int res = 0;10     for (int i = 2; i <= n; i++) 11         res = (res + m) % i;12 13     return res;14 }15 16 int main() {17     size_t n = 10;18     size_t m = 2;19     cout << "The last one is: " << josephus(n, m) << endl;20     return 0;21 }

 


联系
我们