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

题目

思路

排序后寻找中间位置的值，如果数组元素个数是奇数，则直接取中间值，如果是偶数，则取中间两值的平均值，然后遍历一遍数组，每次计算当前元素和中间值差的绝对值并加入到结果中。

题解

题解1

class Solution {
public:
    int minMoves2(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int x;
        int res = 0;
        if(n % 2) { // 奇数
            x = nums[n / 2];
        }
        else{
            int r = nums[n / 2];
            int l = nums[n / 2 - 1];
            x = (r + l) / 2;
        }
        for(int i = 0; i < n; i++){
            res += abs(nums[i] - x);
        }
        return res;
    }
};

时间复杂度：O(n \ logn)，其中 n 是数组中元素的个数，排序时间复杂度是O(n * logn)，计算时间复杂度是O(n)，所以总的时间复杂度是O(n * logn)*
空间复杂度：O(1)

执行用时：8 ms, 在所有 C++ 提交中击败了88.62%的用户

内存消耗：10.7 MB, 在所有 C++ 提交中击败了11.78%的用户

通过测试用例：30 / 30