1.题目
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
2.示例
示例 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
3.思路
一开始我以为都变成平均数变化的次数最少，后来发现不对，变成中位数才能使变化的次数最少。只要知道是向中位数变化就没什么难的了。排序的时候寻找中位数需要用到排序，我用的是官方的大顶堆排序代码，期末考试提前不想复习这个排序了。对于大顶堆排序可以看这个题解的图示
力扣大顶堆排序寻找第k大的数
4.代码
func minMoves2(nums []int) int { addr := len(nums)/2+1 //数组中的第addr个最大数，中位数 mid := findKthLargest(nums,addr) ans := 0 //遍历数组，得到每个数变成中位数需要的次数 for _,v := range nums{ if v>mid { ans = ans + v - mid }else { ans = ans + mid -v } } return ans } //大顶堆法寻找数组中第k大的数 func findKthLargest(nums []int, k int) int { heapSize := len(nums) buildMaxHeap(nums, heapSize) for i := len(nums) - 1; i >= len(nums) - k + 1; i-- { nums[0], nums[i] = nums[i], nums[0] heapSize-- maxHeapify(nums, 0, heapSize) } return nums[0] } func buildMaxHeap(a []int, heapSize int) { for i := heapSize/2; i >= 0; i-- { maxHeapify(a, i, heapSize) } } func maxHeapify(a []int, i, heapSize int) { l, r, largest := i * 2 + 1, i * 2 + 2, i if l < heapSize && a[l] > a[largest] { largest = l } if r < heapSize && a[r] > a[largest] { largest = r } if largest != i { a[i], a[largest] = a[largest], a[i] maxHeapify(a, largest, heapSize) } }
