LeetCode_排序_快速选择_中等_462.最小操作次数使数组元素相等 II

朱雀 2023-10-06 23:51 20阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

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

在一步操作中，你可以使数组中的一个元素加 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.length  
1 <= nums.length <= 105  
\-109 <= nums\[i\] <= 109

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/minimum-moves-to-equal-array-elements-ii

## 2.思路 ##

（1）中位数  
① 先对数组 nums 进行排序；  
② 求出排序后的数组 nums 的中位数 median；  
③ 使所有数组元素相等需要的最少移动数就等于数组 nums 的所有元素与 median 的差的绝对值之和。

至于为什么选择中位数，可以参考[该 LeetCode 用户题解][LeetCode]。

（2）快速选择  
有关快速选择的具体细节可以参考[LeetCode\_排序\_快速选择\_中等\_215.数组中的第K个最大元素][LeetCode_215._K]这篇文章。

相关题目：  
[LeetCode\_逆向思维\_中等\_453.最小操作次数使数组元素相等][LeetCode_453.]

## 3.代码实现（Java） ##

//思路1————中位数
    class Solution {
        
        public int minMoves2(int[] nums) {
        
            int res = 0;
            int n = nums.length;
            Arrays.sort(nums);
            /* 
            	median 为排序后的数组 nums 的中位数，需要注意的是，这里所求的中位数必须是整数
                (1) 如果数组 nums 的长度是奇数时，中位数就是 nums[n / 2]
                (2) 如果数组 nums 的长度是偶数时，按照原来的计算公式 (nums[n / 2] + nums[n / 2 - 1]) / 2.0 
                求出的答案可能不是整数，所以还需要对其做向下取整的操作，最后的结果正好就是 nums[n / 2]
    		*/
            int median = nums[n / 2];
            for (int num : nums) {
        
                res += Math.abs(num - median);
            }
            return res;
        }
    }

//思路2————快速选择
    class Solution {
        
        Random random = new Random();
        
        public int minMoves2(int[] nums) {
        
            int n = nums.length, x = quickSelect(nums, 0, n - 1, n / 2), ret = 0;
            for (int i = 0; i < n; ++i) {
        
                ret += Math.abs(nums[i] - x);
            }
            return ret;
        }
        
        public int quickSelect(int[] nums, int left, int right, int index) {
        
            int q = randomPartition(nums, left, right);
            if (q == index) {
        
                return nums[q];
            } else {
        
                return q < index ? quickSelect(nums, q + 1, right, index) : quickSelect(nums, left, q - 1, index);
            }
        }
        
        public int randomPartition(int[] nums, int left, int right) {
        
            int i = random.nextInt(right - left + 1) + left;
            swap(nums, i, right);
            return partition(nums, left, right);
        }
        
        public int partition(int[] nums, int left, int right) {
        
            int x = nums[right], i = left - 1;
            for (int j = left; j < right; ++j) {
        
                if (nums[j] <= x) {
        
                    ++i;
                    swap(nums, i, j);
                }
            }
            swap(nums, i + 1, right);
            return i + 1;
        }
        
        //交换 nums[i] 和 nums[j] 的值
        public void swap(int[] nums, int i, int j) {
        
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }

[LeetCode]: https://leetcode.cn/problems/minimum-moves-to-equal-array-elements-ii/solution/by-fuxuemingzhu-13z3/
[LeetCode_215._K]: https://blog.csdn.net/weixin_43004044/article/details/119299935
[LeetCode_453.]: https://blog.csdn.net/weixin_43004044/article/details/126170647