C++ 3-line simple solution with explanation:)

  • 0

    The idea is very easy: the number of moves is just the sum of each number that moves to the median number.

    the median number is just n/2 th number in a sorted array. (No matter whether n is odd or even it is always n/2 since it will round it to the whole number anyway )

    so the for loop showing below calculates the distance for each elements to the median number, and the sum of the total moves is the m;

    Problem Solved:)

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

  • 0

    For this problem, you do not need sort everything. You just need find the median. Quick Select is O(n) while Quick Sort is O(nlogn). See https://leetcode.com/problems/kth-largest-element-in-an-array/description/

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.