462. Minimum Moves to Equal Array Elements II

1. Description

Given an integer array nums of length n, make every element equal using as few moves as possible.
Each move changes one selected element by either +1 or -1. Return the minimum number of moves.
The result is guaranteed to fit in a signed 32-bit integer.

2. Example

Example 1

Input: nums = [1,2,3]
Output: 2
Explanation: Increase 1 to 2 and decrease 3 to 2, obtaining [2,2,2] in two moves.

Example 2

Input: nums = [1,10,2,9]
Output: 16
Explanation: Making every element equal to 2 requires 1 + 8 + 0 + 7 = 16 moves, which is minimal.

3. Constraints

• n == nums.length
• 1 <= nums.length <= 10$^5$
• -10$^9$ <= nums[i] <= 10$^9$

4. Solutions

Quickselect

n = nums.size()
Time complexity: O(n) on average
Space complexity: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    int minMoves2(vector<int> &nums) {
        const int n = nums.size();
        int median_index = n / 2;
        nth_element(nums.begin(), nums.begin() + median_index, nums.end());

        int median = nums[median_index];

        int count = 0;
        for (int num : nums) {
            count += abs(num - median);
        }

        return count;
    }
};