LeetCode 462. 最小操作次数使数组元素相等 II【贪心,排序或快速选择】中等

本文主要是介绍LeetCode 462. 最小操作次数使数组元素相等 II【贪心,排序或快速选择】中等,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章中,我不仅会讲解多种解题思路及其优化,还会用多种编程语言实现题解,涉及到通用解法时更将归纳总结出相应的算法模板。

为了方便在PC上运行调试、分享代码文件,我还建立了相关的仓库:https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中,你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等,还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解,还可以一同分享给他人。

由于本系列文章的内容随时可能发生更新变动,欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。

给你一个长度为 n 的整数数组 nums ,返回使所有数组元素相等需要的最小操作数。

在一次操作中,你可以使数组中的一个元素加 1 或者减 1

示例 1:

输入:nums = [1,2,3]
输出:2
解释:
只需要两次操作(每次操作指南使一个元素加 1 或减 1):
[1,2,3]  =>  [2,2,3]  =>  [2,2,2]

示例 2:

输入:nums = [1,10,2,9]
输出:16

提示:

  • n == nums.length
  • 1 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9

题目集合:

  • 453. 最小操作次数使数组元素相等
  • 456. 最小操作次数使数组元素相等 II
  • 2448. 使数组相等的最小开销

解法1 数学+排序

每次可以将一个数加一或者减一,使得所有数组元素相等。凭借直觉可知,将所有数组元素向中间靠拢,所需要的操作次数最少。下面进行证明。

假设数组元素都变成 x x x 时,所需的移动数最少,那么 x x x 需要满足什么性质呢?

为了简化讨论,我们先假定数组长度 n n n 是偶数。我们将数组 nums \textit{nums} nums 从小到大进行排序,然后将数组进行首尾配对,从而划分为多个数对,并将这些数对组成区间 [ nums 0 , nums n − 1 ] , [ nums 1 , nums n − 2 ] , . . . , [ nums n 2 − 1 , nums n 2 ] [\textit{nums}_0, \textit{nums}_{n-1}], [\textit{nums}_1, \textit{nums}_{n-2}], ...,[\textit{nums}_{\frac{n}{2} - 1}, \textit{nums}_{\frac{n}{2}}] [nums0,numsn1],[nums1,numsn2],...,[nums2n1,nums2n]
结论: x x x 同时位于以上区间内时,所需的移动数最少,总移动数为 ∑ i = 0 n 2 − 1 ( nums n − 1 − i − nums i ) \sum_{i=0}^{\frac{n}{2} - 1} (\textit{nums}_{n-1-i} - \textit{nums}_i) i=02n1(numsn1inumsi)

证明:对于某一个区间 [ nums i , nums n − 1 − i ] [\textit{nums}_i, \textit{nums}_{n - 1 -i}] [numsi,numsn1i] ,元素变为 x x x该区间对应的数对所需要的移动数为 ∣ nums n − 1 − i − x ∣ + ∣ nums i − x ∣ ≥ ∣ nums n − 1 − i − x − ( nums i − x ) ∣ = nums n − 1 − i − nums i |\textit{nums}_{n - 1 - i} - x| + |\textit{nums}_i - x| \ge |\textit{nums}_{n - 1 - i} - x - (\textit{nums}_i - x)| = \textit{nums}_{n - 1 - i} - \textit{nums}_i numsn1ix+numsixnumsn1ix(numsix)=numsn1inumsi ,当且仅当 x ∈ [ nums i , nums n − 1 − i ] x\in [\textit{nums}_i, \textit{nums}_{n - 1 -i}] x[numsi,numsn1i]等号成立

在上述区间中,后一个区间是前一个区间的子集,因此只要 x ∈ [ nums n 2 − 1 , nums n 2 ] x \in [\textit{nums}_{\frac{n}{2} - 1}, \textit{nums}_{\frac{n}{2}}] x[nums2n1,nums2n] 就满足要求。

n n n 为奇数时,我们将排序后的数组中间的元素 nums ⌊ n 2 ⌋ \textit{nums}_{\lfloor \frac{n}{2} \rfloor} nums2n 当成区间 [ nums ⌊ n 2 ⌋ , nums ⌊ n 2 ⌋ ] [\textit{nums}_{\lfloor \frac{n}{2} \rfloor}, \textit{nums}_{\lfloor \frac{n}{2} \rfloor}] [nums2n,nums2n] 看待,则 x ∈ [ nums ⌊ n 2 ⌋ , nums ⌊ n 2 ⌋ ] x \in [\textit{nums}_{\lfloor \frac{n}{2} \rfloor}, \textit{nums}_{\lfloor \frac{n}{2} \rfloor}] x[nums2n,nums2n] x = nums ⌊ n 2 ⌋ x= \textit{nums}_{\lfloor \frac{n}{2} \rfloor} x=nums2n 时,所需的移动数最少。

综上所述,所有元素都变成 nums ⌊ n 2 ⌋ \textit{nums}_{\lfloor \frac{n}{2} \rfloor} nums2n 时,所需的移动数最少。

class Solution {
public:int minMoves2(vector<int>& nums) {sort(nums.begin(), nums.end());int n = nums.size(), ans = 0, x = nums[n / 2];for (int i = 0; i < n; ++i) ans += abs(nums[i] - x);// int i = 0, j = nums.size() - 1, ans = 0;// while (i < j) ans += nums[j--] + nums[i++];return ans;}
};

复杂度分析:

  • 时间复杂度: O ( n log ⁡ n ) O(n\log n) O(nlogn),其中 n n n 是数组 nums \textit{nums} nums 的长度。排序需要 O ( n log ⁡ n ) O(n\log n) O(nlogn) 的时间。
  • 空间复杂度: O ( log ⁡ n ) O(\log n) O(logn) 。排序需要 O ( log ⁡ n ) O(\log n) O(logn) 的递归栈空间。

解法2 快速选择

根据方法一的推导, x x x 取数组 nums \textit{nums} nums ⌊ n 2 ⌋ \lfloor \frac{n}{2} \rfloor 2n 小元素(从 0 0 0 开始计数)时,所需要的移动数最少。求解数组第 k k k 小元素可以使用快速选择算法。

class Solution {
public:int quickSelect(vector<int>& nums, int left, int right, int index) {int q = randomPartition(nums, left, right);if (q == index) {return nums[q];} else {return q < index ? quickSelect(nums, q + 1, right, index) : quickSelect(nums, left, q - 1, index);}}inline int randomPartition(vector<int>& nums, int left, int right) {int i = rand() % (right - left + 1) + left;swap(nums[i], nums[right]);return partition(nums, left, right);}inline int partition(vector<int>& nums, int left, int right) {int x = nums[right], i = left - 1;for (int j = left; j < right; ++j) {if (nums[j] <= x) {swap(nums[++i], nums[j]);}}swap(nums[i + 1], nums[right]);return i + 1;}int minMoves2(vector<int>& nums) {srand(time(0));int n = nums.size(), x = quickSelect(nums, 0, n - 1, n / 2), ret = 0;for (int i = 0; i < n; ++i) {ret += abs(nums[i] - x);}return ret;}
};

复杂度分析:

  • 时间复杂度: O ( n ) O(n) O(n) ,其中 n n n 是数组 nums \textit{nums} nums 的长度。快速选择算法的平均时间复杂度为 O ( n ) O(n) O(n)
  • 空间复杂度: O ( log ⁡ n ) O(\log n) O(logn) 。递归栈的平均占用空间为 O ( log ⁡ n ) O(\log n) O(logn)

这篇关于LeetCode 462. 最小操作次数使数组元素相等 II【贪心,排序或快速选择】中等的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/219948

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

如何选择适合孤独症兄妹的学校?

在探索适合孤独症儿童教育的道路上,每一位家长都面临着前所未有的挑战与抉择。当这份责任落在拥有孤独症兄妹的家庭肩上时,选择一所能够同时满足两个孩子特殊需求的学校,更显得尤为关键。本文将探讨如何为这样的家庭做出明智的选择,并介绍星贝育园自闭症儿童寄宿制学校作为一个值得考虑的选项。 理解孤独症儿童的独特性 孤独症,这一复杂的神经发育障碍,影响着儿童的社交互动、沟通能力以及行为模式。对于拥有孤独症兄

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

电脑桌面文件删除了怎么找回来?别急,快速恢复攻略在此

在日常使用电脑的过程中,我们经常会遇到这样的情况:一不小心,桌面上的某个重要文件被删除了。这时,大多数人可能会感到惊慌失措,不知所措。 其实,不必过于担心,因为有很多方法可以帮助我们找回被删除的桌面文件。下面,就让我们一起来了解一下这些恢复桌面文件的方法吧。 一、使用撤销操作 如果我们刚刚删除了桌面上的文件,并且还没有进行其他操作,那么可以尝试使用撤销操作来恢复文件。在键盘上同时按下“C

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

usaco 1.3 Barn Repair(贪心)

思路:用上M块木板时有 M-1 个间隙。目标是让总间隙最大。将相邻两个有牛的牛棚之间间隔的牛棚数排序,选取最大的M-1个作为间隙,其余地方用木板盖住。 做法: 1.若,板(M) 的数目大于或等于 牛棚中有牛的数目(C),则 目测 给每个牛牛发一个板就为最小的需求~ 2.否则,先对 牛牛们的门牌号排序,然后 用一个数组 blank[ ] 记录两门牌号之间的距离,然后 用数组 an

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

C#实战|大乐透选号器[6]:实现实时显示已选择的红蓝球数量

哈喽,你好啊,我是雷工。 关于大乐透选号器在前面已经记录了5篇笔记,这是第6篇; 接下来实现实时显示当前选中红球数量,蓝球数量; 以下为练习笔记。 01 效果演示 当选择和取消选择红球或蓝球时,在对应的位置显示实时已选择的红球、蓝球的数量; 02 标签名称 分别设置Label标签名称为:lblRedCount、lblBlueCount

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

poj 1287 Networking(prim or kruscal最小生成树)

题意给你点与点间距离,求最小生成树。 注意点是,两点之间可能有不同的路,输入的时候选择最小的,和之前有道最短路WA的题目类似。 prim代码: #include<stdio.h>const int MaxN = 51;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int P;int prim(){bool vis[MaxN];