462. 最小操作次数使数组元素相等 II——【Leetcode每日一题】
2023-09-14 09:01:27 时间
462. 最小操作次数使数组元素相等 II
给你一个长度为 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 = = n u m s . l e n g t h n == nums.length n==nums.length
- 1 < = n u m s . l e n g t h < = 1 0 5 1 <= nums.length <= 10^5 1<=nums.length<=105
- − 1 0 9 < = n u m s [ i ] < = 1 0 9 - 10^9 <= nums[i] <= 10^9 −109<=nums[i]<=109
思路:
每次可以对一个数组元素加一或者减一,求最小的改变次数。
这是个典型的相遇问题,移动距离最小的方式是所有元素都移动到中位数。理由如下:
- 设
m
为中位数。a
和b
是m
两边的两个元素,且b > a
。 - 要使
a
和b
相等,它们总共移动的次数为b - a
,这个值等于(b - m) + (m - a)
, - 也就是把这两个数移动到中位数的移动次数。
设数组长度为 N
,则可以找到 N/2
对 a
和 b
的组合,使它们都移动到 m
的位置。
代码:(Java、C++)
Java
import java.util.Arrays;
public class MinMoves2 {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] nums = {1, 10, 2, 9};
System.out.println(minMoves2(nums));
}
public static int minMoves2(int[] nums) {
Arrays.sort(nums);
int l = 0, h = nums.length - 1;
int moves = 0;
while(l < h) {
moves += nums[h--] - nums[l++];
}
return moves;
}
}
C++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class MinMoves2 {
public:
int minMoves2(vector<int>& nums) {
sort(nums.begin(), nums.end());
int l = 0, h = nums.size() - 1;
int moves = 0;
while (l < h)
{
moves += nums[h--] - nums[l++];
}
return moves;
}
};
int main() {
MinMoves2 m;
vector<int> nums = {1,10,2,9 };
cout << m.minMoves2(nums) << endl;
system("pause");
return 0;
}
运行结果:
复杂度分析:
- 时间复杂度:
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn),其中
n
是数组nums
的长度。排序需要 O ( n l o g n ) O(nlogn) O(nlogn)的时间。 - 空间复杂度: O ( l o g n ) O(logn) O(logn)。排序需要 O ( l o g n ) O(logn) O(logn)的递归栈空间。
题目来源:力扣。
注:仅供学习参考, 如有不足,欢迎指正!
相关文章
- Java实现 LeetCode 724 寻找数组的中心索引(暴力)
- Java实现 LeetCode 684 冗余连接(并查集)
- Java实现 LeetCode 560 和为K的子数组(某著名排序大法改编)
- Java实现 LeetCode 554 砖墙(缝隙可以放在数组?)
- Java实现 LeetCode 457 环形数组循环
- Java实现 LeetCode 279 完全平方数
- Java实现 LeetCode 80 删除排序数组中的重复项 II(二)
- Java实现 LeetCode 24 两两交换链表中的节点
- 【数组&双指针】LeetCode 142. 环形链表 II【中等】
- LeetCode(49): 字母异位词分组
- LeetCode(14):最长公共前缀
- LeetCode-1814. 统计一个数组中好对子的数目【哈希表】
- LeetCode-817. 链表组件【哈希表,链表,数组】
- LeetCode-1598. 文件夹操作日志搜集器【栈,字符串,数组】
- LeetCode-878. 第 N 个神奇数字【数学,二分查找,找规律】
- leetcode-1331. 数组序号转换
- 【LeetCode 26】删除排序数组中的重复项
- 【LeetCode Python实现】26. 删除排序数组中的重复项(简单)
- LeetCode Merge k Sorted Lists 解决报告
- leetcode-1 Two Sum 找到数组中两数字和为指定和
- [LeetCode]Surrounded Regions
- leetcode 447. Number of Boomerangs
- 【LeetCode】乘积最大子数组