将元素分配到两个数组中 II

You are given a 1-indexed array of integers nums of length n.

We define a function greaterCount such that greaterCount(arr, val) returns the number of elements in arr that are strictly greater than val.

You need to distribute all the elements of nums between two arrays arr1 and arr2 using n operations. In the first operation, append nums[1] to arr1. In the second operation, append nums[2] to arr2. Afterwards, in the ith operation:

• If greaterCount(arr1, nums[i]) > greaterCount(arr2, nums[i]), append nums[i] to arr1.
• If greaterCount(arr1, nums[i]) < greaterCount(arr2, nums[i]), append nums[i] to arr2.
• If greaterCount(arr1, nums[i]) == greaterCount(arr2, nums[i]), append nums[i] to the array with a lesser number of elements.
• If there is still a tie, append nums[i] to arr1.

The array result is formed by concatenating the arrays arr1 and arr2. For example, if arr1 == [1,2,3] and arr2 == [4,5,6], then result = [1,2,3,4,5,6].

Return the integer array result.

 

Example 1:

Input: nums = [2,1,3,3]
Output: [2,3,1,3]
Explanation: After the first 2 operations, arr1 = [2] and arr2 = [1].
In the 3rd operation, the number of elements greater than 3 is zero in both arrays. Also, the lengths are equal, hence, append nums[3] to arr1.
In the 4th operation, the number of elements greater than 3 is zero in both arrays. As the length of arr2 is lesser, hence, append nums[4] to arr2.
After 4 operations, arr1 = [2,3] and arr2 = [1,3].
Hence, the array result formed by concatenation is [2,3,1,3].

Example 2:

Input: nums = [5,14,3,1,2]
Output: [5,3,1,2,14]
Explanation: After the first 2 operations, arr1 = [5] and arr2 = [14].
In the 3rd operation, the number of elements greater than 3 is one in both arrays. Also, the lengths are equal, hence, append nums[3] to arr1.
In the 4th operation, the number of elements greater than 1 is greater in arr1 than arr2 (2 > 1). Hence, append nums[4] to arr1.
In the 5th operation, the number of elements greater than 2 is greater in arr1 than arr2 (2 > 1). Hence, append nums[5] to arr1.
After 5 operations, arr1 = [5,3,1,2] and arr2 = [14].
Hence, the array result formed by concatenation is [5,3,1,2,14].

Example 3:

Input: nums = [3,3,3,3]
Output: [3,3,3,3]
Explanation: At the end of 4 operations, arr1 = [3,3] and arr2 = [3,3].
Hence, the array result formed by concatenation is [3,3,3,3].

 

Constraints:

• 3 <= n <= 105
• 1 <= nums[i] <= 109

/*
 * 思路：
 * 1. 创建一个函数 greaterCount 用于计算数组中严格大于给定值的元素数量。
 * 2. 初始化两个数组 arr1 和 arr2，分别用于存储 nums 的元素。
 * 3. 遍历 nums 数组，根据条件将元素添加到 arr1 或 arr2。
 * 4. 最后将 arr1 和 arr2 连接起来形成结果数组并返回。
 */

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

public class SolutionStream {
    public int[] divideAndMerge(int[] nums) {
        List<Integer> arr1 = new ArrayList<>();
        List<Integer> arr2 = new ArrayList<>();
        
        for (int i = 0; i < nums.length; i++) {
            if (i % 2 == 0) {
                arr1.add(nums[i]);
            } else {
                arr2.add(nums[i]);
            }
            if (i >= 2) {
                long count1 = greaterCount(arr1, nums[i]);
                long count2 = greaterCount(arr2, nums[i]);
                if (count1 > count2) {
                    arr1.add(nums[i]);
                } else if (count1 < count2) {
                    arr2.add(nums[i]);
                } else {
                    if (arr1.size() <= arr2.size()) {
                        arr1.add(nums[i]);
                    } else {
                        arr2.add(nums[i]);
                    }
                }
            }
        }
        
        return IntStream.concat(arr1.stream().mapToInt(i -> i), arr2.stream().mapToInt(i -> i)).toArray();
    }

    private long greaterCount(List<Integer> arr, int val) {
        return arr.stream().filter(num -> num > val).count();
    }
}

该题解采用了二进制索引树（Binary Indexed Tree，BIT）来高效地维护和查询数组中特定值的计数信息。首先，创建一个值到索引的映射（v2i），将数组中的元素映射到一个连续的索引范围内，并按值排序。这个映射用于在BIT中更新和查询位置。对于数组中的每个元素，基于其在BIT中的计数值以及当前两个数组（arr1和arr2）的长度，决定将元素添加到哪一个数组。使用BIT可以快速计算出任意元素值大于当前元素值的元素数量。这种方法允许我们在对数时间内处理每个元素的插入操作，从而有效地解决问题。

O(n log m)

O(m + n)