LC.P1823[找出游戏的获胜者]

方法一：队列+模拟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int findTheWinner(int n, int k) {
        Deque<Integer> 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(nk)$
  • 空间复杂度：$O(n)$

方法二：数学+递归

1
2
3
4
5
6
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)$

方法三：数学+迭代

1
2
3
4
5
6
7
8
9
class Solution {
    public int findTheWinner(int n, int k) {
        int ans = 1;
        for (int i = 2; i <= n; i++) {
            ans = (k + ans - 1) % i + 1;
        }
        return ans;
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(1)$