力扣加加 - 努力做西湖区最好的算法题解
lucifer 的博客
Github
公众号
搜索文档…
introduction
第一章 - 算法专题
第二章 - 91 天学算法
第三章 - 精选题解
第四章 - 高频考题(简单)
第五章 - 高频考题(中等)
第六章 - 高频考题(困难)
LCP 20. 快速公交
LCP 21. 追逐游戏
Number Stream to Intervals
Triple-Inversion
Kth-Pair-Distance
Minimum-Light-Radius
Largest Equivalent Set of Pairs
Ticket-Order.md
Connected-Road-to-Destination
0004. 寻找两个正序数组的中位数
0023. 合并 K 个升序链表
0025. K 个一组翻转链表
0030. 串联所有单词的子串
0032. 最长有效括号
0042. 接雨水
0052. N 皇后 II
0057. 插入区间
0065. 有效数字
0084. 柱状图中最大的矩形
0085. 最大矩形
0087. 扰乱字符串
0124. 二叉树中的最大路径和
0128. 最长连续序列
0132. 分割回文串 II
0140. 单词拆分 II
0145. 二叉树的后序遍历
0146. LRU 缓存机制
0154. 寻找旋转排序数组中的最小值 II
0212. 单词搜索 II
0239. 滑动窗口最大值
0295. 数据流的中位数
0297. 二叉树的序列化与反序列化
0301. 删除无效的括号
0312. 戳气球
330. 按要求补齐数组
0335. 路径交叉
0460. LFU 缓存
0472. 连接词
0480. 滑动窗口中位数
0483. 最小好进制
0488. 祖玛游戏
0493. 翻转对
0664. 奇怪的打印机
0679. 24 点游戏
0715. Range 模块
0726. 原子的数量
0768. 最多能完成排序的块 II
0805. 数组的均值分割
0839. 相似字符串组
0887. 鸡蛋掉落
0895. 最大频率栈
0975. 奇偶跳
0995. K 连续位的最小翻转次数
1032. 字符流
1168. 水资源分配优化
1178. 猜字谜
1203. 项目管理
1255. 得分最高的单词集合
1345. 跳跃游戏 IV
1449. 数位成本和为目标值的最大数字
1494. 并行课程 II
1521. 找到最接近目标值的函数值
1526. 形成目标数组的子数组最少增加次数
1649. 通过指令创建有序数组
1671. 得到山形数组的最少删除次数
1707. 与数组中元素的最大异或值
1713. 得到子序列的最少操作次数
1723. 完成所有工作的最短时间
1787. 使所有区间的异或结果为零
1835. 所有数对按位与结果的异或和
1871. 跳跃游戏 VII
1872. 石子游戏 VIII
1883. 准时抵达会议现场的最小跳过休息次数
1970. 你能穿过矩阵的最后一天
2009. 使数组连续的最少操作数
2025. 分割数组的最多方案数
2030. 含特定字母的最小子序列
2102. 序列顺序查询
2209. 用地毯覆盖后的最少白色砖块
2281.sum-of-total-strength-of-wizards
2306. 公司命名
5254. 卖木头块
5999. 统计数组中好三元组数目
后序
由
GitBook
提供支持
2009. 使数组连续的最少操作数
题目地址(2009. 使数组连续的最少操作数)
https://leetcode-cn.com/problems/minimum-number-of-operations-to-make-array-continuous/
题目描述
给你一个整数数组 nums 。每一次操作中,你可以将 nums 中 任意 一个元素替换成 任意 整数。
如果 nums 满足以下条件,那么它是 连续的 :
nums 中所有元素都是 互不相同 的。
nums 中 最大 元素与 最小 元素的差等于 nums.length - 1 。
比方说,nums = [4, 2, 5, 3] 是 连续的 ,但是 nums = [1, 2, 3, 5, 6] 不是连续的 。
请你返回使 nums 连续 的 最少 操作次数。
示例 1:
输入:nums = [4,2,5,3]
输出:0
解释:nums 已经是连续的了。
示例 2:
输入:nums = [1,2,3,5,6]
输出:1
解释:一个可能的解是将最后一个元素变为 4 。
结果数组为 [1,2,3,5,4] ,是连续数组。
示例 3:
输入:nums = [1,10,100,1000]
输出:3
解释:一个可能的解是:
- 将第二个元素变为 2 。
- 将第三个元素变为 3 。
- 将第四个元素变为 4 。
结果数组为 [1,2,3,4] ,是连续数组。
提示:
1 <= nums.length <= 105
1 <= nums[i] <= 109
前置知识
二分
公司
暂无
思路
由于最终的数组长度一定是原数组长度。 因此题目让我们找最少操作数,其实等价于找最多保留多少个数不变,这样我们就可以通过最少的操作数使得数组连续。
朴素的思路是枚举所有的区间 [a,b] 其中 a 和 b 为区间 [min(nums),max(nums)] 中的两个数。这种思路的时间复杂度是 $O(v^2)$,其中 v 为 nums 的值域。看一下数据范围,很明显会超时。
我们可以先对数组排序,这样就可以二分找答案,使得时间复杂度降低。看下时间复杂度排序的时间是可以允许的,因此这种解决可以 ac。
具体地:
对数组去重
对数组排序
遍历 nums,对于每一个 num 我们都二分找到最左和最右的
满足值域差小于等于 old_n 的索引
,其中 old_n 为去重前的 nums 长度。简单来说,我们需要找到满足值在 [x,num] 范围的最左 x 和满足值在 [num,y] 范围的最右 y
满足两个值域范围的区间我们找到了,那么答案区间长度的最大值,也就是 n - 区间长度中的
最小值
具体参考下方代码。
关键点
反向思考,题目要找最少操作数,其实就是找最多保留多少个数
代码
语言支持:Python3
Python3 Code:
import
bisect
class
Solution
:
def
minOperations
(
self
,
nums
:
List
[
int
])
->
int
:
ans
=
on
=
len
(
nums
)
nums
=
list
(
set
(
nums
))
nums
.
sort
()
n
=
len
(
nums
)
for
i
,
v
in
enumerate
(
nums
):
r
=
bisect
.
bisect_right
(
nums
,
v
+
on
-
1
)
l
=
bisect
.
bisect_left
(
nums
,
v
-
on
+
1
)
ans
=
min
(
ans
,
n
-
(
r
-
i
),
n
-
(
i
-
l
+
1
))
return
ans
+
(
on
-
n
)
复杂度分析
令 n 为数组长度。
时间复杂度:$O(nlogn)$
空间复杂度:$O(n)$
此题解由
力扣刷题插件
自动生成。
力扣的小伙伴可以
关注我
,这样就会第一时间收到我的动态啦~
以上就是本文的全部内容了。大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:
https://github.com/azl397985856/leetcode
。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。
Could not load image
以前
1970. 你能穿过矩阵的最后一天
下一个
2025. 分割数组的最多方案数
最近更新
10mo ago
复制链接
大纲
题目地址(2009. 使数组连续的最少操作数)
题目描述
前置知识
公司
思路
关键点
代码