国外做电商网站有哪些,佛山网站建设公司哪专业,广州注册公司流程及资料,外包兼职平台题目
462. 最小操作次数使数组元素相等 II
中等
相关标签
数组 数学 排序
给你一个长度为 n 的整数数组 nums #xff0c;返回使所有数组元素相等需要的最小操作数。
在一次操作中#xff0c;你可以使数组中的一个元素加 1 或者减 1 。 示例 1#xff1a;
输入返回使所有数组元素相等需要的最小操作数。
在一次操作中你可以使数组中的一个元素加 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.length1 nums.length 105-109 nums[i] 109
思路和解题方法 // 计算使数组所有元素相等所需的最小移动次数这是对 minMoves2 函数功能的简要描述。 sort(nums.begin(),nums.end());使用 C 的标准库函数 sort 对数组 nums 进行升序排序。 int n nums.size();获取数组 nums 的长度即元素个数。 int ans 0, x nums[n/2];初始化结果变量 ans 为 0并取中位数作为目标值 x。这里利用了数组已经排序过的特性直接取排序后的中间值作为目标值。 for(int i 0;in;i)遍历数组 nums对每个元素进行处理。 ans abs(nums[i] - x);累加每个元素与目标值 x 的差的绝对值到结果变量 ans 中。这里通过计算每个元素与目标值的差的绝对值来累加移动次数因为我们的目标是让所有元素相等所以需要将每个元素移动到目标值 x 所需的步数。 return ans;将累加结果 ans 作为最小移动次数返回。 复杂度 时间复杂度: O(n * logn) 时间复杂度为O(n log n)其中n是输入数组nums的长度。这是因为在代码中使用了sort函数对数组进行排序其时间复杂度为O(n log n)。接下来的for循环需要线性时间O(n)来遍历整个数组因此整体的时间复杂度为O(n log n n)即O(n log n)。 空间复杂度 O(1) 空间复杂度则为O(1)因为除了输入数组之外代码中并没有使用额外的辅助空间所以空间复杂度是常数级的为O(1)。 c 代码
class Solution {
public:// 计算使数组所有元素相等所需的最小移动次数int minMoves2(vectorint nums) {// 对数组进行排序sort(nums.begin(),nums.end());// 获取数组长度int n nums.size();// 初始化结果变量为0并取中位数作为目标值int ans 0, x nums[n/2];// 遍历数组累加每个元素与目标值的差的绝对值for(int i 0;in;i){ans abs(nums[i] - x);}// 返回累加结果作为最小移动次数return ans;}
};Java代码
class Solution {// 计算使数组所有元素相等所需的最小移动次数public int minMoves2(int[] nums) {// 对数组进行排序Arrays.sort(nums);// 获取数组长度int n nums.length;// 初始化结果变量为0并取中位数作为目标值int ret 0, x nums[n / 2];// 遍历数组累加每个元素与目标值的差的绝对值for (int i 0; i n; i) {ret Math.abs(nums[i] - x);}// 返回累加结果作为最小移动次数return ret;}
}觉得有用的话可以点点赞支持一下。
如果愿意的话关注一下。会对你有更多的帮助。 每天都会不定时更新哦 人 。
