leetcode 462. Minimum Moves to Equal Array Elements II

朴灿烈づ我的快乐病毒、 2022-06-13 06:36 101阅读 0赞

# 1.题目 #

Given a non-empty integer array, find the minimum number of moves required to make all array elements equal, where a move is incrementing a selected element by 1 or decrementing a selected element by 1.  
一个非空整数组，要求找到最小的移动步数使得整个数组的元素相等。  
一次移动可以将一个元素加1或减1

Example:

Input:  
\[1,2,3\]

Output:  
2

Explanation:  
\[1,2,3\] => \[2,2,3\] => \[2,2,2\]

# 2.分析 #

关键在于找到数组的中位数。将每个元素通过多次移动到中位数的总步数是最小的。  
找中位数有两种方式：  
1)对数组排序，取中间位置的数,复杂度O(nlogn)  
2)使用QuickSelect ，复杂度O(n)  
3)nth\_element,stl部分排序算法。我们只在意整个数组中第k大的数是多少k=length/2

# 3.代码 #

QuickSelect

class Solution {
    public:
        int quickselect(vector<int> nums, int k, int start, int end) {
            int low = start;
            int high = end;
            int pivot = nums[(end + start) / 2];
            while (low <= high) {
                while (nums[low] < pivot)
                    ++low;
                while (nums[high] > pivot)
                    --high;
                if (low <= high) {
                    swap(nums[low], nums[high]);
                    ++low;
                    --high;
                }
            }
            if (high > start&&high >= k)
                return quickselect(nums, k, start,high);
            if (low < end&&low <= k)
                return quickselect(nums, k, low, end);
            return nums[k];
        }
        int minMoves2(vector<int>& nums) {
            int sum = 0;
            int median = quickselect(nums, nums.size() / 2, 0, nums.size()-1);
            for (auto n : nums)
                sum += abs(n - median);
            return sum;
        }
    };

nth\_element

class Solution {
    public:
        int minMoves2(vector<int>& nums) {
            int sum = 0;
            auto it = nums.begin() + nums.size() / 2;
            nth_element(nums.begin(), it, nums.end());
            int median = *it;
            for (auto n : nums)
                sum += abs(n - median);
            return sum;
        }
    };

快排

class Solution {
    public:
        int minMoves2(vector<int>& nums) {
            sort(nums.begin(), nums.end());
            int mid = nums[nums.size() / 2];
            int ans = 0;
            for (auto n : nums) 
                ans += abs(n - mid);
            return ans;
        }
    };