最小数字游戏

You are given a 0-indexed integer array nums of even length and there is also an empty array arr. Alice and Bob decided to play a game where in every round Alice and Bob will do one move. The rules of the game are as follows:

• Every round, first Alice will remove the minimum element from nums, and then Bob does the same.
• Now, first Bob will append the removed element in the array arr, and then Alice does the same.
• The game continues until nums becomes empty.

Return the resulting array arr.

 

Example 1:

Input: nums = [5,4,2,3]
Output: [3,2,5,4]
Explanation: In round one, first Alice removes 2 and then Bob removes 3. Then in arr firstly Bob appends 3 and then Alice appends 2. So arr = [3,2].
At the begining of round two, nums = [5,4]. Now, first Alice removes 4 and then Bob removes 5. Then both append in arr which becomes [3,2,5,4].

Example 2:

Input: nums = [2,5]
Output: [5,2]
Explanation: In round one, first Alice removes 2 and then Bob removes 5. Then in arr firstly Bob appends and then Alice appends. So arr = [5,2].

 

Constraints:

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100
• nums.length % 2 == 0

/* 
 * 思路：
 * 1. 将 nums 数组排序。
 * 2. 使用 Stream API 将数组前半部分倒序添加到 arr，然后将后半部分按顺序添加到 arr。 
 */
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class GameSolutionStream {
    public static List<Integer> playGame(int[] nums) {
        return IntStream.concat(
                    Arrays.stream(nums).sorted().skip(nums.length / 2).boxed(), // Bob 添加
                    Arrays.stream(nums).sorted().limit(nums.length / 2).boxed().sorted((a, b) -> b - a) // Alice 添加
                ).collect(Collectors.toList());
    }

    public static void main(String[] args) {
        int[] nums = {5, 4, 2, 3};
        System.out.println(playGame(nums)); // 输出: [3, 2, 5, 4]
    }
}

题解首先对输入数组 nums 进行逆序排序，即从大到小排序。这样，每次通过 nums.pop() 取出的将是数组中当前的最小值。由于 Alice 先移除最小元素，随后 Bob 移除次小元素，这两个元素被加入到结果数组 result 中时，Bob 加入的元素应该在 Alice 加入的元素之前。因此，每次迭代中，先从逆序排序的 nums 中 pop 出两个元素（首先是最小的，然后是次小的），然后先将次小的元素（Bob 移除的）加入到 result，再加入最小的元素（Alice 移除的）。整个过程重复进行，直到 nums 为空。

O(n log n)

O(n)