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

Categories:

题目描述
思路分析
1. 解法一：排序取中位数（推荐）
相似题目

题目描述

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

思路分析

解法一：排序取中位数（推荐）

核心思路：

目标值取数组中位数可使绝对差之和最小。

排序后选取中位数，累加所有元素与中位数的绝对差。

复杂度分析：

时间复杂度：O(n log n)，其中 n 表示数组长度。

空间复杂度：O(1) 额外空间（排序可能原地进行）。

import java.util.Arrays;

class Solution {
    public int minMoves2(int[] nums) {
        Arrays.sort(nums);
        int median = nums[nums.length / 2];
        long moves = 0;

        for (int num : nums) {
            moves += Math.abs(num - median);
        }

        return (int) moves;
    }
}

import "sort"

func minMoves2(nums []int) int {
	sort.Ints(nums)
	median := nums[len(nums)/2]
	moves := 0

	for _, num := range nums {
		if num >= median {
			moves += num - median
		} else {
			moves += median - num
		}
	}

	return moves
}

相似题目

题目	难度	考察点
203. 移除链表元素	简单	双指针
296. 最佳的碰头地点	困难	中位数
1480. 一维数组的动态和	简单	前缀和
1700. 无法吃午餐的学生数量	简单	模拟
1710. 卡车上的最大单元数	简单	贪心

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/77966385