1.题目基本信息

1.1.题目描述

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

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

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

1.2.题目地址

https://leetcode.cn/problems/minimum-moves-to-equal-array-elements-ii/description/

2.解题方法

2.1.解题思路

思路1：排序+中位数

思路2：快速排序。本地关键求中位数，即第n//2小的元素；记录每次分隔后的pivot的索引index，如果index==n//2,，那么此时的pivot即为要求的中位数，如果index>n//2，则在nums[0:index]返回继续找pivot，如果index<n//2，则在nums[index:]中继续找pivot

2.2.解题步骤

快速排序步骤：

• 第一步，构建分隔函数，返回最终pivot的索引

• 第二步，迭代获取第n//2小的元素

3.解题代码

python3代码

class Solution:
    def minMoves2(self, nums: List[int]) -> int:
        # 思路2：快速排序。本地关键求中位数，即第n//2小的元素；记录每次分隔后的pivot的索引index，如果index==n//2,，那么此时的pivot即为要求的中位数，如果index>n//2，则在nums[0:index]返回继续找pivot，如果index<n//2，则在nums[index:]中继续找pivot
        n = len(nums)
        # 第一步，构建分隔函数，返回最终pivot的索引
        def partition(low:int, high:int) -> int:
            pivot = nums[low]
            while low < high:
                while low < high and nums[high] >= pivot:
                    high -= 1
                nums[low] = nums[high]
                while low < high and nums[low] <= pivot:
                    low += 1
                nums[high] = nums[low]
            nums[low] = pivot
            return low
        # 第二步，迭代获取第n//2小的元素
        k = n // 2
        low, high = 0, n - 1
        while True:
            index = partition(low, high)
            if index == k:
                return sum(abs(num - nums[k]) for num in nums)
            elif index > k:
                high = index - 1
            else:
                low = index + 1

    def minMoves2_1(self, nums: List[int]) -> int:
        # 思路1：排序+中位数
        nums.sort()
        mid = nums[len(nums) // 2]
        return sum(abs(num - mid) for num in nums)

4.执行结果