What is the main technique used to solve Distribute Elements Into Two Arrays II?

The main technique used in this problem is the Binary Indexed Tree (BIT), which allows efficient tracking of counts of elements greater than a given value.

How does the Binary Indexed Tree help with the distribution process?

The Binary Indexed Tree allows for efficient querying and updating of counts of elements greater than a specific value, enabling quick decision-making for each insertion into the arrays.

What is the time complexity of the optimal solution for Distribute Elements Into Two Arrays II?

The time complexity of the optimal solution is O(n log n) due to the use of Binary Indexed Tree for insertion and querying operations.

Can we use a Segment Tree instead of a Binary Indexed Tree?

Yes, a Segment Tree can be used instead of a Binary Indexed Tree, though it may be less efficient for this specific problem.

How do we handle tie-breakers in this problem?

When both arrays have the same count of elements greater than the current value, the decision is based on the array sizes, where the element is appended to the smaller array.

#3072

Hard

auto_awesome数组·结合·二分·indexed·树

LeetCode 题解工作台

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

给你一个下标从 1 开始、长度为 n 的整数数组 nums 。现定义函数 greaterCount ，使得 greaterCount(arr, val) 返回数组 arr 中严格大于 val 的元素数量。你需要使用 n 次操作，将 nums 的所有元素分配到两个数组 arr1 和 arr2 中…

数组树状数组线段树模拟

题目描述

给你一个下标从 1 开始、长度为 n 的整数数组 nums 。

现定义函数 greaterCount ，使得 greaterCount(arr, val) 返回数组 arr 中 严格大于 val 的元素数量。

你需要使用 n 次操作，将 nums 的所有元素分配到两个数组 arr1 和 arr2 中。在第一次操作中，将 nums[1] 追加到 arr1 。在第二次操作中，将 nums[2] 追加到 arr2 。之后，在第 i 次操作中：

如果 greaterCount(arr1, nums[i]) > greaterCount(arr2, nums[i]) ，将 nums[i] 追加到 arr1 。
如果 greaterCount(arr1, nums[i]) < greaterCount(arr2, nums[i]) ，将 nums[i] 追加到 arr2 。
如果 greaterCount(arr1, nums[i]) == greaterCount(arr2, nums[i]) ，将 nums[i] 追加到元素数量较少的数组中。
如果仍然相等，那么将 nums[i] 追加到 arr1 。

连接数组 arr1 和 arr2 形成数组 result 。例如，如果 arr1 == [1,2,3] 且 arr2 == [4,5,6] ，那么 result = [1,2,3,4,5,6] 。

返回整数数组 result 。

示例 1：

输入：nums = [2,1,3,3]
输出：[2,3,1,3]
解释：在前两次操作后，arr1 = [2] ，arr2 = [1] 。
在第 3 次操作中，两个数组中大于 3 的元素数量都是零，并且长度相等，因此，将 nums[3] 追加到 arr1 。
在第 4 次操作中，两个数组中大于 3 的元素数量都是零，但 arr2 的长度较小，因此，将 nums[4] 追加到 arr2 。
在 4 次操作后，arr1 = [2,3] ，arr2 = [1,3] 。
因此，连接形成的数组 result 是 [2,3,1,3] 。

示例 2：

输入：nums = [5,14,3,1,2]
输出：[5,3,1,2,14]
解释：在前两次操作后，arr1 = [5] ，arr2 = [14] 。
在第 3 次操作中，两个数组中大于 3 的元素数量都是一，并且长度相等，因此，将 nums[3] 追加到 arr1 。
在第 4 次操作中，arr1 中大于 1 的元素数量大于 arr2 中的数量（2 > 1），因此，将 nums[4] 追加到 arr1 。
在第 5 次操作中，arr1 中大于 2 的元素数量大于 arr2 中的数量（2 > 1），因此，将 nums[5] 追加到 arr1 。
在 5 次操作后，arr1 = [5,3,1,2] ，arr2 = [14] 。
因此，连接形成的数组 result 是 [5,3,1,2,14] 。

示例 3：

输入：nums = [3,3,3,3]
输出：[3,3,3,3]
解释：在 4 次操作后，arr1 = [3,3] ，arr2 = [3,3] 。
因此，连接形成的数组 result 是 [3,3,3,3] 。

提示：

3 <= n <= 10⁵
1 <= nums[i] <= 10⁹

lightbulb

解题思路

方法一：离散化 + 树状数组

我们可以用两个树状数组 tree1 和 tree2 分别维护 arr1 和 arr2 中小于等于某个数的元素个数。每一次，我们在树状数组中查询小于等于当前数的元素个数，那么大于当前数的元素个数就是当前数组的长度减去查询的结果。然后我们就可以根据这个差值来决定将当前数加入到哪个数组中。

由于题目中给出的数的范围很大，所以我们需要对这些数进行离散化。我们可以将这些数排序后去重，然后用二分查找来找到每个数在排序后的数组中的位置。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是数组 nums 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

class BinaryIndexedTree:
    __slots__ = "n", "c"

    def __init__(self, n: int):
        self.n = n
        self.c = [0] * (n + 1)

    def update(self, x: int, delta: int) -> None:
        while x <= self.n:
            self.c[x] += delta
            x += x & -x

    def query(self, x: int) -> int:
        s = 0
        while x:
            s += self.c[x]
            x -= x & -x
        return s


class Solution:
    def resultArray(self, nums: List[int]) -> List[int]:
        st = sorted(set(nums))
        m = len(st)
        tree1 = BinaryIndexedTree(m + 1)
        tree2 = BinaryIndexedTree(m + 1)
        tree1.update(bisect_left(st, nums[0]) + 1, 1)
        tree2.update(bisect_left(st, nums[1]) + 1, 1)
        arr1 = [nums[0]]
        arr2 = [nums[1]]
        for x in nums[2:]:
            i = bisect_left(st, x) + 1
            a = len(arr1) - tree1.query(i)
            b = len(arr2) - tree2.query(i)
            if a > b:
                arr1.append(x)
                tree1.update(i, 1)
            elif a < b:
                arr2.append(x)
                tree2.update(i, 1)
            elif len(arr1) <= len(arr2):
                arr1.append(x)
                tree1.update(i, 1)
            else:
                arr2.append(x)
                tree2.update(i, 1)
        return arr1 + arr2

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for an understanding of Binary Indexed Tree (BIT) and its application to dynamic counting.
question_mark
Evaluate the candidate’s ability to simulate the problem conditions with efficient data structures.
question_mark
Check for a clear explanation of handling the array insertion logic while maintaining efficiency.

warning

常见陷阱

外企场景

error
Failing to efficiently track counts of greater elements using an appropriate data structure.
error
Incorrectly handling tie-breakers when both arrays have the same count of greater elements.
error
Not managing the balance between the two arrays properly, leading to incorrect results.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Change the distribution rule, for example, append to the array with fewer elements instead of the one with fewer greater elements.
arrow_right_alt
Instead of using a Binary Indexed Tree, try using a Segment Tree for the counting operation.
arrow_right_alt
Increase the number of arrays from two to three or more, with different insertion conditions.

help

常见问题

外企场景

继续练习

#3161 物块放置查询 #3187 数组中的峰值 #2940 找到 Alice 和 Bob 可以相遇的建筑