找出转圈游戏输家

There are n friends that are playing a game. The friends are sitting in a circle and are numbered from 1 to n in clockwise order. More formally, moving clockwise from the ith friend brings you to the (i+1)th friend for 1 <= i < n, and moving clockwise from the nth friend brings you to the 1st friend.

The rules of the game are as follows:

1st friend receives the ball.

• After that, 1st friend passes it to the friend who is k steps away from them in the clockwise direction.
• After that, the friend who receives the ball should pass it to the friend who is 2 * k steps away from them in the clockwise direction.
• After that, the friend who receives the ball should pass it to the friend who is 3 * k steps away from them in the clockwise direction, and so on and so forth.

In other words, on the ith turn, the friend holding the ball should pass it to the friend who is i * k steps away from them in the clockwise direction.

The game is finished when some friend receives the ball for the second time.

The losers of the game are friends who did not receive the ball in the entire game.

Given the number of friends, n, and an integer k, return the array answer, which contains the losers of the game in the ascending order.

 

Example 1:

Input: n = 5, k = 2
Output: [4,5]
Explanation: The game goes as follows:
1) Start at 1st friend and pass the ball to the friend who is 2 steps away from them - 3rd friend.
2) 3rd friend passes the ball to the friend who is 4 steps away from them - 2nd friend.
3) 2nd friend passes the ball to the friend who is 6 steps away from them  - 3rd friend.
4) The game ends as 3rd friend receives the ball for the second time.

Example 2:

Input: n = 4, k = 4
Output: [2,3,4]
Explanation: The game goes as follows:
1) Start at the 1st friend and pass the ball to the friend who is 4 steps away from them - 1st friend.
2) The game ends as 1st friend receives the ball for the second time.

 

Constraints:

• 1 <= k <= n <= 50

/*
 * Problem Description:
 * n friends are playing a game sitting in a circle, numbered from 1 to n in clockwise order. 
 * The 1st friend starts with the ball and passes it to the friend k steps away in the clockwise direction.
 * The game continues where the friend who receives the ball passes it to the friend 2*k steps away, then 3*k, and so on.
 * The game ends when a friend receives the ball for the second time.
 * The goal is to return the list of friends who never received the ball.
 */

import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class FriendsGameStream {
    public static List<Integer> findLosers(int n, int k) {
        boolean[] received = new boolean[n]; // Tracks who received the ball
        int currentIndex = 0; // Starting from the 1st friend (index 0)
        int passCount = 1; // Initial pass count
        while (true) {
            if (received[currentIndex]) {
                break; // Game ends when a friend receives the ball for the second time
            }
            received[currentIndex] = true;
            currentIndex = (currentIndex + passCount * k) % n;
            passCount++;
        }
        return IntStream.range(0, n)
                .filter(i -> !received[i])
                .mapToObj(i -> i + 1) // Converting to 1-based index
                .collect(Collectors.toList());
    }

    public static void main(String[] args) {
        System.out.println(findLosers(5, 2)); // Output: [4, 5]
        System.out.println(findLosers(4, 4)); // Output: [2, 3, 4]
    }
}

此题解采用模拟的方式来跟踪球的传递过程。首先，初始化一个布尔数组 `friend` 来标记每个朋友是否接过球。数组的索引表示朋友的编号（从0开始，即编号1的朋友是 `friend[0]`）。游戏从第1个朋友开始，因此 `friend[0]` 初始化为 `True`。随后，使用变量 `temp` 来记录当前持球者的位置，并用变量 `i` 来记录传球的轮次。游戏继续进行，直到一个朋友第二次接到球，此时游戏结束。最后，遍历 `friend` 数组，将未接过球的朋友编号（加1后）添加到结果列表 `result` 中。

O(n)

O(n)