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

链接：3072.将元素分配到两个数组中II
难度：Hard
标签：树状数组、线段树、数组、模拟
简介：返回整数数组 result 。

题解 1 - python

• 编辑时间：2024-06-05
• 执行用时：6345ms
• 内存消耗：33.59MB
• 编程语言：python
• 解法介绍：有序数组存储后模拟。

from sortedcontainers import SortedList
    class Solution:
        def resultArray(self, nums: List[int]) -> List[int]:
            res1 = [nums[0]]
            sorted1 = SortedList(res1)
            res2 = [nums[1]]
            sorted2 = SortedList(res2)
            for num in nums[2:]:
                cnt1 = len(res1) - bisect_right(sorted1, num)
                cnt2 = len(res2) - bisect_right(sorted2, num)
                if cnt1 > cnt2 or (cnt1 == cnt2 and len(res1) <= len(res2)):
                    res1.append(num)
                    sorted1.add(num)
                else:
                    res2.append(num)
                    sorted2.add(num)
            return res1 + res2