453-最小操作次数使数组元素相等

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

给你一个长度为 n 的整数数组，每次操作将会使 n - 1 个元素增加 1 。返回让数组所有元素相等的最小操作次数。

示例 1：

输入：nums = [1,2,3]
输出：3
解释：
只需要3次操作（注意每次操作会增加两个元素的值）：
[1,2,3]  =>  [2,3,3]  =>  [3,4,3]  =>  [4,4,4]

method

对n-1个数都加1，相当于对1个数减1，所以就找出数组中的最小值，累加每个值到最小的距离就行

int minMoves(vector<int>& nums) {
    int nMin = INT_MAX;
    for (auto n : nums) {
        nMin = min(nMin, n); 
    }
    int res = 0;
    for (auto n : nums) {
        res += (n - nMin);
    }
    return res;
}

---

LeetCode 462. 最少移动次数使数组元素相等 II

给定一个非空整数数组，找到使所有数组元素相等所需的最小移动数，其中每次移动可将选定的一个元素加1或减1。 您可以假设数组的长度最多为10000。

例如:

输入:
[1,2,3]
输出:
2
说明：只有两个动作是必要的（记得每一步仅可使其中一个元素加1或减1）： 
[1,2,3]  =>  [2,2,3]  =>  [2,2,2]

method 1

需要找到这么一个数，使得所有数到这个数的距离之和最小，即中位数

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

method 2: 快速排序

应用215-数组中的第k个最大元素中的思想，找中位数就相当于找数组中第n/2大的元素

int quickSelect(vector<int>& nums, int l, int r, int index) {
    int ret = partition(nums, l, r);
    if (ret == index) {
        return nums[ret];
    }
    else if (ret < index) {
        return quickSelect(nums, ret + 1, r, index);
    }
    else return quickSelect(nums, l, ret - 1, index);
}
int partition(vector<int>& nums, int l, int r) {
    int pivot = nums[r];
    int i = l;
    for (int j = l; j <= r; j++) {
        if (nums[j] < pivot) {
            swap(nums[i], nums[j]);
            i++;
        }
    }
    swap(nums[i], nums[r]);
    return i;
}
int minMoves2(vector<int>& nums) {
    int n = nums.size();
    int k = n / 2;
    int mid = quickSelect(nums, 0, n - 1, k);   // 找中位数
    int res = 0;
    for (auto n : nums) {
        res += abs(mid - n);
    }
    return res;
}