910.最小差值 II
【LetMeFly】910.最小差值 II:贪心(排序)-小数大数分界线枚举(思考过程详解)
力扣题目链接:https://leetcode.cn/problems/smallest-range-ii/
给你一个整数数组 nums
,和一个整数 k
。
对于每个下标 i
(0 <= i < nums.length
),将 nums[i]
变成 nums[i] + k
或 nums[i] - k
。
nums
的 分数 是 nums
中最大元素和最小元素的差值。
在更改每个下标对应的值之后,返回 nums
的最小 分数 。
示例 1:
输入:nums = [1], k = 0 输出:0 解释:分数 = max(nums) - min(nums) = 1 - 1 = 0 。
示例 2:
输入:nums = [0,10], k = 2 输出:6 解释:将数组变为 [2, 8] 。分数 = max(nums) - min(nums) = 8 - 2 = 6 。
示例 3:
输入:nums = [1,3,6], k = 3 输出:3 解释:将数组变为 [4, 6, 3] 。分数 = max(nums) - min(nums) = 6 - 3 = 3 。
提示:
1 <= nums.length <= 104
0 <= nums[i] <= 104
0 <= k <= 104
解题方法:贪心(排序)
这次每个数必须得变,考虑数组中最小的数$m$和最大$M$的数:
- 如果$m$和$M$同时变大/同时变小,则差值$diff=M-m$;
- 如果$m$变小$M$变大,则差值变大$diff=M-m+2k\geq M-m$;
- 如果$m$变大$M$变小,则差值为$diff=abs((M-k)-(m+k))=abs(M-m-2k)$。
如果$m$很小$M$很大,那么那么$m$变$M$变小的话差值会变小;如果$m$和$M$相差本来不大,那么$m$变大而$M$变小的话$diff$反而可能会变大。怎么办呢?
其实不难发现,除了最小的数和最大的数,其他较小的数和较大的数也是这样的关系。
我们可以先对数组排个序,然后枚举“小数大数的分界线”。分界线左边的数视为“小数”并且全部$+k$,分界线右边的数视为“大数”并且全部$-k$。
在所有的方案中,差值最小的那个即为所求。
对于一个方案,如何快速计算$diff$呢?
假设$nums[0]$到$nums[i]$每个数$+k$,$nums[i + 1]$到$nums[n - 1]$每个数$-k$,那么:
数组中最大的数为$nums[i] + k$或者$nums[n - 1] - k$,最小的数为$nums[i + 1] - k$或$nums[0] + k$。
因此$diff=\max(nums[i] + k, nums[len(nums) - 1] - k) - \min(nums[i + 1] - k, nums[0] + k)$。
- 时间复杂度$O(n\log n)$,其中$n=len(nums)$
- 空间复杂度$O(\log n)$,时空复杂度的开销主要来自排序
AC代码
C++
1 |
|
Go
1 |
|
Java
1 |
|
Python
1 |
|
同步发文于CSDN和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/143136177