java LeetCode刷题稍有难度的贪心构造算法
作者:宫水三叶的刷题日记 发布时间:2022-01-06 20:56:21
题目描述
这是 LeetCode 上的 768. 最多能完成排序的块 II ,难度为 困难。
Tag : 「贪心」
这个问题和“最多能完成排序的块”相似,但给定数组中的元素可以重复,输入数组最大长度为 200020002000,其中的元素最大为 10810^8108。
arr
是一个可能包含重复元素的整数数组,我们将这个数组分割成几个“块”,并将这些块分别进行排序。之后再连接起来,使得连接的结果和按升序排序后的原数组相同。
我们最多能将数组分成多少块?
示例 1:
输入: arr = [5,4,3,2,1]
输出: 1
解释:
将数组分成2块或者更多块,都无法得到所需的结果。
例如,分成 [5, 4], [3, 2, 1] 的结果是 [4, 5, 1, 2, 3],这不是有序的数组。
示例 2:
输入: arr = [2,1,3,4,4]
输出: 4
解释:
我们可以把它分成两块,例如 [2, 1], [3, 4, 4]。
然而,分成 [2, 1], [3], [4], [4] 可以得到最多的块数。
注意:
arr
的长度在 [1,2000][1, 2000][1,2000] 之间。
arr[i]
的大小在 [0,108][0, 10^8][0,108] 之间。
贪心 + 构造
一种容易想到的构造方法,是与目标序列(已排升序的数组 clone
)做区间比较。
由于题目要求尽可能划分出多的区间,我们可以从前往后处理 arr
和 clone
时统计区间内数的情况,若有 arr[i...j]
和 clone[i...j]
词频完全相同,可知 arr[i...j]
可通过内部排序调整为 clone[i...j]
,此时我们将范围 [i...j][i...j][i...j] 划分为一个区间,然后继续往后处理直到整个数组处理完。
Java 代码:
class Solution {
public int maxChunksToSorted(int[] arr) {
int[] clone = arr.clone();
Arrays.sort(clone);
int n = arr.length, ans = 0;
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0, tot = 0; i < n; i++) {
int a = arr[i], b = clone[i];
if (map.getOrDefault(a, 0) == -1) tot--;
else if (map.getOrDefault(a, 0) == 0) tot++;
map.put(a, map.getOrDefault(a, 0) + 1);
if (map.getOrDefault(b, 0) == 1) tot--;
else if (map.getOrDefault(b, 0) == 0) tot++;
map.put(b, map.getOrDefault(b, 0) - 1);
if (tot == 0) ans++;
}
return ans;
}
}
TypeScript 代码:
function maxChunksToSorted(arr: number[]): number {
let clone = [...arr].sort((a,b)=>a-b)
let n = arr.length, ans = 0
const map = new Map<number, number>()
for (let i = 0, tot = 0; i < n; i++) {
const a = arr[i], b = clone[i]
if (!map.has(a)) map.set(a, 0)
if (map.get(a) == 0) tot++
else if (map.get(a) == -1) tot--;
map.set(a, map.get(a) + 1)
if (!map.has(b)) map.set(b, 0)
if (map.get(b) == 0) tot++
else if (map.get(b) == 1) tot--
map.set(b, map.get(b) - 1)
if (tot == 0) ans++
}
return ans
};
时间复杂度:O(nlogn)
空间复杂度:O(n)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.768
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour… 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
来源:https://juejin.cn/post/7195586451870072891
猜你喜欢
- 简介我们在使用flutter的过程中,有时候需要控制某些组件是否展示,一种方法是将这个组件从render tree中删除,这样这个组件就相当
- Flink中设计了用户自定义函数体系(User Defined Function,UDF),开发人员实现业务逻辑就是开发UDF。一、环境对象
- 1. 什么是RESTREST全称是Representational State Transfer,中文意思是表述(编者注:通常译为表征)性状
- java中的JsonSerializer用法背景今天在写项目的时候遇到一个问题,项目中有个类中有创建时间和更新时间两个属性,但是单位在后端用
- [程序中使用的数据结构和符号说明]HitBrick类GreenBallThread控制小球路线xUp,yUp,bouncing定义变量存储1
- 前言这篇博客介绍Java环境的配置,主要是安装JDK,以及path、JAVA_hOME、CLASSPAT的配置,还会介绍配置这些的原因。一.
- Java BufferWriter写文件之后文件是空的或者数据不全在编程的过程中,读写文件是非常常见的操作,在这里我问介绍一下最近我遇到的集
- 动态内存管理为什么存在动态内存分配我们到现在为止掌握的是什么样的内存开辟方式呢//创建一个变量int val = 20; &n
- 开篇本文主要来探讨一下 redis 的单线程模型,文章前半部分会先引用某网络课程讲解的内容(图片+语言描述),后半部分是本人粗略阅读 red
- 1、阿里云DNS的SDK依赖<dependency> <groupId>com.aliyu
- properties配置文件如下:human.name=Mr.Yuhuman.age=21human.gender=male如何把prope
- Spring boot项目结合docker容器用,打了个jar包,启动的时候竟然说:no main manifest attribute,
- 本文实例为大家分享了Java从服务端下载Excel模板文件的具体实现代码,供大家参考,具体内容如下方法一 (2021年01月更新)生成exc
- 现在提起Android开发工具,大多人第一个想到的肯定是Android Studio。谷歌专门为Android开发者推出的这款IDE,以其强
- 这里简单介绍了一些常用的属性,以及一些术语的解释和举例说明,不太全面,希望读者多多补充。1.重载:函数名相同,参数的个数或参数类型不同; p
- 第一种给容器中的组件加上@ConfigurationProperties注解即可测试:@Component@ConfigurationPro
- 由于项目需要做一些图形展示,所以就想到了使用Directx和OpenGL来绘图,但项目准备使用C#来开发(大家比较熟悉C#),在网上看了相关
- pom.xml<dependency> <groupId>org.springframework.bo
- 在实际应用中,大家使用的密码可以说多种多样,但是无论有多少,其组成不遑是有可打印字符组成的,我们可以认为class CreateDic{ p
- Java环境配置原理详解1.Jdk安装目录文件说明:一般jdk安装目录及路径 \Java\jdk1.7.0_79\lib,里面主要包含以下文