模板网站建设全过程,成都建设学校网站,flarum wordpress,沧州网站建设公司排名462. 最小操作次数使数组元素相等 II
给你一个长度为 n 的整数数组 nums #xff0c;返回使所有数组元素相等需要的最小操作数。
在一次操作中#xff0c;你可以使数组中的一个元素加 1 或者减 1 。
示例 1#xff1a; 输入#xff1a;nums [1,2,3] 输出#xff1a;2 …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 提示
nnums.lengthn nums.lengthnnums.length1nums.length1051 nums.length 10^51nums.length105−109nums[i]109- 10^9 nums[i] 10^9−109nums[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 stubint[] 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(vectorint 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;vectorint nums {1,10,2,9 };cout m.minMoves2(nums) endl;system(pause);return 0;
}运行结果 复杂度分析
时间复杂度O(nlogn)O(nlogn)O(nlogn)其中 n 是数组 nums 的长度。排序需要 O(nlogn)O(nlogn)O(nlogn)的时间。空间复杂度O(logn)O(logn)O(logn)。排序需要 O(logn)O(logn)O(logn)的递归栈空间。
题目来源力扣。
注仅供学习参考 如有不足欢迎指正
