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

相关文章

Java操作Word文档的全面指南

《Java操作Word文档的全面指南》在Java开发中,操作Word文档是常见的业务需求,广泛应用于合同生成、报表输出、通知发布、法律文书生成、病历模板填写等场景,本文将全面介绍Java操作Word文... 目录简介段落页头与页脚页码表格图片批注文本框目录图表简介Word编程最重要的类是org.apach

C# 比较两个list 之间元素差异的常用方法

《C#比较两个list之间元素差异的常用方法》:本文主要介绍C#比较两个list之间元素差异,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1. 使用Except方法2. 使用Except的逆操作3. 使用LINQ的Join,GroupJoin

Python实现对阿里云OSS对象存储的操作详解

《Python实现对阿里云OSS对象存储的操作详解》这篇文章主要为大家详细介绍了Python实现对阿里云OSS对象存储的操作相关知识,包括连接,上传,下载,列举等功能,感兴趣的小伙伴可以了解下... 目录一、直接使用代码二、详细使用1. 环境准备2. 初始化配置3. bucket配置创建4. 文件上传到os

MySQL查询JSON数组字段包含特定字符串的方法

《MySQL查询JSON数组字段包含特定字符串的方法》在MySQL数据库中,当某个字段存储的是JSON数组,需要查询数组中包含特定字符串的记录时传统的LIKE语句无法直接使用,下面小编就为大家介绍两种... 目录问题背景解决方案对比1. 精确匹配方案(推荐)2. 模糊匹配方案参数化查询示例使用场景建议性能优

关于集合与数组转换实现方法

《关于集合与数组转换实现方法》:本文主要介绍关于集合与数组转换实现方法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、Arrays.asList()1.1、方法作用1.2、内部实现1.3、修改元素的影响1.4、注意事项2、list.toArray()2.1、方

mysql表操作与查询功能详解

《mysql表操作与查询功能详解》本文系统讲解MySQL表操作与查询,涵盖创建、修改、复制表语法,基本查询结构及WHERE、GROUPBY等子句,本文结合实例代码给大家介绍的非常详细,感兴趣的朋友跟随... 目录01.表的操作1.1表操作概览1.2创建表1.3修改表1.4复制表02.基本查询操作2.1 SE

c++中的set容器介绍及操作大全

《c++中的set容器介绍及操作大全》:本文主要介绍c++中的set容器介绍及操作大全,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录​​一、核心特性​​️ ​​二、基本操作​​​​1. 初始化与赋值​​​​2. 增删查操作​​​​3. 遍历方

MySQL追踪数据库表更新操作来源的全面指南

《MySQL追踪数据库表更新操作来源的全面指南》本文将以一个具体问题为例,如何监测哪个IP来源对数据库表statistics_test进行了UPDATE操作,文内探讨了多种方法,并提供了详细的代码... 目录引言1. 为什么需要监控数据库更新操作2. 方法1:启用数据库审计日志(1)mysql/mariad

springboot如何通过http动态操作xxl-job任务

《springboot如何通过http动态操作xxl-job任务》:本文主要介绍springboot如何通过http动态操作xxl-job任务的问题,具有很好的参考价值,希望对大家有所帮助,如有错... 目录springboot通过http动态操作xxl-job任务一、maven依赖二、配置文件三、xxl-

一文详解Java Stream的sorted自定义排序

《一文详解JavaStream的sorted自定义排序》Javastream中的sorted方法是用于对流中的元素进行排序的方法,它可以接受一个comparator参数,用于指定排序规则,sorte... 目录一、sorted 操作的基础原理二、自定义排序的实现方式1. Comparator 接口的 Lam