Java&C++题解与拓展——leetcode1823.找出游戏的获胜者【约瑟夫环】

• 题目要求
• 思路一：模拟
• • Java
  • C++
• 思路二：递归
• • Java
  • C++
• 思路三：迭代
• • Java
  • C++
  • Rust
• 总结

【这个问题似乎叫做约瑟夫环】

• 用一个栈来模拟，将经过的小伙伴都重新加入队列，停驻位置小伙伴pop出去。

class Solution {
    public int findTheWinner(int n, int k) {
        Queue queue = new ArrayDeque();
        for(int i = 1; i <= n; i++)
            queue.offer(i);
        while(queue.size() > 1) {
            for(int i = 1; i < k; i++)
                queue.offer(queue.poll());
            queue.poll();
        }
        return queue.peek();
    }
}

• 时间复杂度： O ( n k ) O(nk) O(nk)
• 空间复杂度： O ( n ) O(n) O(n)

• 用一个数组 o u t out out记录小伙伴淘汰与否，记录已淘汰人数 c n t cnt cnt，直至只剩一人；
• 循环遍历寻找第 k k k个未被淘汰的人，将其淘汰，从下一个未被淘汰的人开始下一次遍历。
• 遍历时起始下标为 0 0 0，结果中起始下标为 1 1 1，注意转换。

class Solution {
public:
    int findTheWinner(int n, int k) {
        bool out[n + 10];
        memset(out, false, n + 10);
        int cnt = 0, cur = 0;
        while(cnt != n - 1) { // 淘汰人数！=n-1
            for(int j = 0; j < k - 1; j++) {
                cur++;
                while(out[cur % n]) // 第k个未被淘汰的人
                    cur++;
            }
            out[cur % n] = true;
            cnt++;
            cur++;
            while(out[cur % n]) // 从下一个未被淘汰的人开始
                cur++;
        }
        return (cur % n) + 1;
    }
};

• 时间复杂度： O ( n 2 ) O(n^2) O(n2)，要淘汰 n − 1 n-1 n−1个人，每淘汰一个人最多需遍历 n n n个人。
• 空间复杂度： O ( n ) O(n) O(n)

• 数学推导出规律直接递归；
• 约瑟夫环
  • 函数简写为f(n, k)，表示淘汰 n n n个人里的第 k k k个；
  • 下一次淘汰的起始下标与本次相差 k k k；
  • 所以 f ( n , k ) = k + f ( n − 1 , k ) f(n,k)=k+f(n-1,k) f(n,k)=k+f(n−1,k)
• 由于起始下标差异，结果为0时应返回 n n n，可以先 − 1 -1 −1模后再加回来（Java），或者条件运算符判断（C++）。

class Solution {
    public int findTheWinner(int n, int k) {
        if(n == 1)
            return 1;
        return (k + findTheWinner(n - 1, k) - 1) % n + 1;
    }
}

• 时间复杂度： O ( n ) O(n) O(n)
• 空间复杂度： O ( n ) O(n) O(n)，递归的栈开销

class Solution {
public:
    int findTheWinner(int n, int k) {
        if(n == 1)
            return 1;
        int res = (k + findTheWinner(n - 1, k)) % n;
        return res == 0 ? n : res;
    }
};

• 时间复杂度： O ( n ) O(n) O(n)
• 空间复杂度： O ( n ) O(n) O(n)，递归的栈开销

传统艺能之递归改迭代，省栈空间，思路一样。

class Solution {
    public int findTheWinner(int n, int k) {
        int res = 1;
        for(int i = 2; i <= n; i++)
            res = (k + res - 1) % i + 1;
        return res;
    }
}

• 时间复杂度： O ( n ) O(n) O(n)
• 空间复杂度： O ( 1 ) O(1) O(1)

class Solution {
public:
    int findTheWinner(int n, int k) {
        int res = 1;
        for(int i = 2; i <= n; i++)
            res = (k + res - 1) % i + 1;
        return res;
    }
};

• 时间复杂度： O ( n ) O(n) O(n)
• 空间复杂度： O ( 1 ) O(1) O(1)

浅学一下rust

impl Solution {
    pub fn find_the_winner(n: i32, k: i32) -> i32 {
        (2..=n).fold(1, |ref mut res, i| {
            *res = (k + *res - 1) % i + 1;
            *res
        })
    }
}

算是简单的题目，推导出规律很好实现。

最近想学学Rust就浅浅cv+了解一下……