3072.将元素分配到两个数组中 II [困难]
题目：
给你一个下标从 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**5
- 1 <= nums[i] <= 10**9
题目分析:
这道题的话，题目还是比较容易理解的，就是对复杂度要求有点高，毕竟数据量摆在这呢，大致的思路就是模拟，模拟他分配的过程。 在这道题中引入了SortedList函数，下面先讲解一下SortedList函数：
SortedList是Python语言中的一个模块，用于实现排序列表数据结构的类。这个模块提供了一个名为SortedList的类，可以很方便地对列表进行排序操作。sortedlist模块包含了对列表的各种操作，如插入、删除、查找、切片等，并且能够保持列表中的元素是有序的状态。通过使用sortedlist模块，可以更容易地对列表进行排序和查找操作，提高代码的效率和可读性。下面是代码示例：
from sortedlist import SortedList # 创建一个空的排序列表 slist = SortedList() # 向排序列表中插入元素 slist.add(5) slist.add(2) slist.add(8) slist.add(3) # 打印排序后的列表 print(slist) # 输出: SortedList([2, 3, 5, 8]) # 使用index方法查找元素的索引 index = slist.index(5) print(index) # 输出: 2 # 使用remove方法删除列表中的元素 slist.remove(3) print(slist) # 输出: SortedList([2, 5, 8])
总体来说，这个函数是列表的一种，他可以实现加入每一个元素都对齐进行插入排序，且复杂度很低，可以达到O（nlogn），对于这道题他可以很方便的帮我们计算出来比nums[i]绝对大的数字有几个。
代码实现：
from sortedcontainers import SortedList class Solution: def resultArray(self, nums: List[int]) -> List[int]: arr1=SortedList() arr2=SortedList() arr1.add(nums[0]) arr2.add(nums[1]) res1=[nums[0]] res2=[nums[1]] def ar(ls, h): return len(ls) - ls.bisect_right(h) for i in range(2,len(nums)): k1=ar(arr1,nums[i]) k2=ar(arr2,nums[i]) # print(k1,k2) if k1<k2: arr2.add(nums[i]) res2.append(nums[i]) elif k1==k2: if len(arr1)<=len(arr2): arr1.add(nums[i]) res1.append(nums[i]) # print(len(arr1),len(arr2)) else: arr2.add(nums[i]) res2.append(nums[i]) else: arr1.add(nums[i]) res1.append(nums[i]) res1.extend(res2) return res1
总结：
此函数采用排序列表数据结构，以O(log(n))时间复杂度插入元素。然后，通过比较当前插入元素与先前插入的元素的相对位置，选择在哪个列表中添加插入元素。最终返回混合列表，其中元素按顺序添加。具体步骤如下：
- 创建两个空的排序列表arr1和arr2，分别用来存储比较小的元素和比较大的元素。
- 将列表中的前两个元素分别加入到arr1和arr2中，同时分别将这两个元素也添加到两个结果列表res1和res2中。
- 定义一个辅助函数ar(ls, h)，用来计算列表ls中比元素h大的元素的数量。
- 从第3个元素开始遍历列表，对每个元素执行以下操作：
- 分别计算该元素在arr1和arr2中大于该元素的元素数量，保存为k1和k2。
- 如果k1 < k2，将该元素添加到arr2和res2中。
- 如果k1 == k2，比较arr1和arr2的长度，将该元素添加到较短的列表中，并将该元素添加到res1或res2中。
- 如果k1 > k2，将该元素添加到arr1和res1中。
- 合并res1和res2，并返回结果。
通过这种方法，可以将元素按照大小有序地插入到两个列表中，最终得到一个按照排好序的结果列表。
