力扣每日一题 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,并返回结果。

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

目录
相关文章
|
4月前
|
传感器 人工智能 API
通义灵码2.5深度评测:编程智能体与MCP工具的革新体验
通义灵码2.5通过“智能体+MCP”组合,重新定义了AI编码助手的边界。其价值不仅在于代码生成效率,更在于通过工具链整合和环境感知,推动开发流程向“声明式编程”演进。对于开发者而言,它既是提升效率的利器,也是探索AI辅助开发边界的实验场。
366 8
|
存储 前端开发 JavaScript
揭秘!JavaScript本地存储的四大绝技:从Cookie到IndexedDB,让你的Web应用秒变数据存储高手,轻松应对各种挑战!
【8月更文挑战第4天】JavaScript为核心前端技术,提供多样本地存储方案以优化用户体验与减少服务器负载。首先,Cookie虽用于基本数据如登录状态,但受大小限制及安全性影响。接着,Web Storage中的LocalStorage持久存储不变数据,SessionStorage则限于单次会话。更进一步,IndexedDB作为全面数据库解决方案,支持复杂数据操作但使用较复杂。每种方式根据应用需求各有优势。
255 9
|
11月前
|
NoSQL 关系型数据库 MySQL
Tomcat、MySQL、Redis最大支持说明
综上所述,Tomcat、MySQL、Redis的并发处理能力均非固定值,而是通过合理的配置与优化策略,结合系统硬件资源,共同决定了它们在实际应用中的表现。开发者应根据应用的具体需求和资源条件,对这些组件进行细致的调优,以达到最佳性能表现。
150 1
|
11月前
|
Web App开发 JSON JavaScript
深入浅出:Node.js后端开发入门与实践
【10月更文挑战第4天】在这个数字信息爆炸的时代,了解如何构建一个高效、稳定的后端系统对于开发者来说至关重要。本文将引导你步入Node.js的世界,通过浅显易懂的语言和逐步深入的内容组织,让你不仅理解Node.js的基本概念,还能掌握如何使用它来构建一个简单的后端服务。从安装Node.js到实现一个“Hello World”程序,再到处理HTTP请求,文章将带你一步步走进Node.js的大门。无论你是初学者还是有一定经验的开发者,这篇文章都将为你打开一扇通往后端开发新世界的大门。
|
存储 Java 测试技术
Java零基础教学(10):包装类
【9月更文挑战第1天】Java零基础教学篇,手把手实践教学!
144 1
|
前端开发 Python
分享86个CSS3特效,总有一款适合您
分享86个CSS3特效,总有一款适合您
207 1
|
域名解析 弹性计算 监控
使用云效将项目代码部署到云服务器ECS的体验评测
本文详述了使用阿里云云效和ECS搭建企业门户网站的解决方案,包括引导文档、部署流程、一键与手动部署的优缺点以及部署中可能遇到的问题。文中建议阿里云改进文档更新及时性,增强流程指引清晰度,提供更具体的错误信息,并增加实时监控、报警功能及性能优化建议。此外,呼吁建立更多用户交流平台以提升用户体验。
217 1
|
测试技术 Go iOS开发
8千字详解Go1.20稳定版(一)
8千字详解Go1.20稳定版(一)
579 1
|
存储 关系型数据库 MySQL
MySQL中select 查询完整语法与子查询使用
MySQL中select 查询完整语法与子查询使用
1834 1
|
JavaScript Shell 开发工具
使用vuepress从零开始搭建我的技术文档|已部署到线上
几天前为了深入学习JS我手写了一个JS工具库,并且发布到了npm上 我把具体步骤,从零搭建再到发布上线的全部细节都写在这这一片文章上了:手写了一个JS工具库并发布到npm 既然已经写了JS工具库,那必须要有文档呀,要不然谁知道怎么使用!!! 所以今天这篇文章就介绍一下怎么使用vuepress2.x搭建一个文档,内容不深,小白也能看懂,因为我只是小小的写了一下 ^_^嘿嘿 文档效果可以点击此处查看☞:LearnJTs文档
809 1
使用vuepress从零开始搭建我的技术文档|已部署到线上