462. 最小操作次数使数组元素相等 II

🟠   🔖  数组 数学 排序  🔗 力扣 LeetCode

题目

Given an integer array nums of size n, return the minimum number of moves required to make all array elements equal.

In one move, you can increment or decrement an element of the array by 1.

Test cases are designed so that the answer will fit in a 32-bit integer.

Example 1:

Input: nums = [1,2,3]

Output: 2

Explanation:

Only two moves are needed (remember each move increments or decrements one element):

[1 ,2,3] => [2,2,3] => [2,2,2]

Example 2:

Input: nums = [1,10,2,9]

Output: 16

Constraints:

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

题目大意

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

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

测试用例经过设计以使答案在 32 位 整数范围内。

示例 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

解题思路

思路一：排序

1. 排序 nums，确定中位数 mid = nums[n/2]。
2. 遍历 nums，计算所有元素变成 mid 需要的步数。

复杂度分析

• 时间复杂度：O(n log n)，排序 O(n log n)，求和 O(n)。
• 空间复杂度：O(1)，只使用了常数级变量。

---

思路二：快速选择排序

我们只需要找到中位数，不需要完全排序。因此，可以使用快速选择算法（QuickSelect）在 O(n) 时间内找到中位数。

• 采用**分区（partition）**的方式，每次将一个元素放到正确的位置。
• 但 只递归处理一侧（与快速排序不同）。

复杂度分析

• 时间复杂度：O(n)，排序 O(n)，求和 O(n)。
• 空间复杂度：O(1)，只使用了常数级变量。

代码

排序

/**
 * @param {number[]} nums
 * @return {number}
 */
var minMoves2 = function (nums) {
	nums.sort((a, b) => a - b);
	const mid = nums[(nums.length / 2) | 0]; // 选取中位数
	return nums.reduce((acc, cur) => acc + Math.abs(cur - mid), 0);
};

快速选择排序

/**
 * @param {number[]} nums
 * @return {number}
 */
var minMoves2 = function (nums) {
	const n = nums.length;

	// 快速选择算法: 找到第 k 小的元素（k = n // 2）
	function quickSelect(left, right, k) {
		if (left >= right) return nums[left];

		let pivot = partition(left, right);
		if (pivot === k) return nums[pivot];
		return pivot < k
			? quickSelect(pivot + 1, right, k)
			: quickSelect(left, pivot - 1, k);
	}

	// Lomuto partition
	function partition(left, right) {
		let pivot = nums[right],
			i = left;
		for (let j = left; j < right; j++) {
			if (nums[j] < pivot) {
				[nums[i], nums[j]] = [nums[j], nums[i]];
				i++;
			}
		}
		[nums[i], nums[right]] = [nums[right], nums[i]];
		return i;
	}

	// 找到中位数
	const mid = quickSelect(0, n - 1, Math.floor(n / 2));

	// 计算总步数
	return nums.reduce((acc, num) => acc + Math.abs(num - mid), 0);
};

相关题目

题号	标题	题解	标签	难度	力扣
296	最佳的碰头地点 🔒		数组 数学 矩阵 1+	🔴	🀄️ 🔗
453	最小操作次数使数组元素相等	[✓]	数组 数学	🟠	🀄️ 🔗
2033	获取单值网格的最小操作数	[✓]	数组 数学 矩阵 1+	🟠	🀄️ 🔗
2171	拿出最少数目的魔法豆		贪心 数组 枚举 2+	🟠	🀄️ 🔗
2448	使数组相等的最小开销		贪心 数组 二分查找 2+	🔴	🀄️ 🔗
2602	使数组元素全部相等的最少操作次数		数组 二分查找 前缀和 1+	🟠	🀄️ 🔗
2967	使数组成为等数数组的最小代价		贪心 数组 数学 2+	🟠	🀄️ 🔗