题目要求

在这里插入图片描述

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

思路一：模拟

Java

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

class Solution {
    public int findTheWinner(int n, int k) {
        Queue<Integer> queue = new ArrayDeque<Integer>();
        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 (n)$

C++

用一个数组 $o u t$ 记录小伙伴淘汰与否，记录已淘汰人数 $c n t$ ，直至只剩一人；
循环遍历寻找第 $k$ 个未被淘汰的人，将其淘汰，从下一个未被淘汰的人开始下一次遍历。
遍历时起始下标为 $0$ ，结果中起始下标为 $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)$ ，要淘汰 $n ? 1$ 个人，每淘汰一个人最多需遍历 $n$ 个人。
空间复杂度： $O (n)$

思路二：递归

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

Java

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)$ ，递归的栈开销

C++

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)$ ，递归的栈开销

思路三：迭代

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

Java

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 (1)$

C++

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 (1)$

Rust

浅学一下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
        })
    }
}