力扣每日一题 6/5

简介: 力扣每日一题 6/5

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))时间复杂度插入元素。然后,通过比较当前插入元素与先前插入的元素的相对位置,选择在哪个列表中添加插入元素。最终返回混合列表,其中元素按顺序添加。具体步骤如下:

  1. 创建两个空的排序列表arr1和arr2,分别用来存储比较小的元素和比较大的元素。
  2. 将列表中的前两个元素分别加入到arr1和arr2中,同时分别将这两个元素也添加到两个结果列表res1和res2中。
  3. 定义一个辅助函数ar(ls, h),用来计算列表ls中比元素h大的元素的数量。
  4. 从第3个元素开始遍历列表,对每个元素执行以下操作:
  • 分别计算该元素在arr1和arr2中大于该元素的元素数量,保存为k1和k2。
  • 如果k1 < k2,将该元素添加到arr2和res2中。
  • 如果k1 == k2,比较arr1和arr2的长度,将该元素添加到较短的列表中,并将该元素添加到res1或res2中。
  • 如果k1 > k2,将该元素添加到arr1和res1中。
  1. 合并res1和res2,并返回结果。

       通过这种方法,可以将元素按照大小有序地插入到两个列表中,最终得到一个按照排好序的结果列表。

目录
相关文章
|
1月前
【LeetCode-每日一题】移动零
【LeetCode-每日一题】移动零
26 1
|
5月前
|
存储
力扣每日一题 6/9
力扣每日一题 6/9
42 5
|
5月前
力扣每日一题 6/2
力扣每日一题 6/2
37 3
|
5月前
|
存储 人工智能 算法
力扣每日一题 6/4
力扣每日一题 6/4
35 3
|
5月前
力扣每日一题 6/1
力扣每日一题 6/1
41 3
|
5月前
力扣每日一题 6/8
力扣每日一题 6/8
31 3
|
5月前
力扣每日一题 6/3
力扣每日一题 6/3
31 3
|
5月前
力扣每日一题 5/27
力扣每日一题 5/27
30 2
|
5月前
|
机器学习/深度学习
力扣每日一题 5/31
力扣每日一题 5/31
29 2
|
5月前
|
JavaScript
力扣每日一题 5/26
力扣每日一题 5/26
36 2