C++ Solution - Easy to Understand


  • 1
    class Solution {
    public:
    int minMoves2(vector<int>& nums) {
      sort(nums.begin(),nums.end()); 
      
      /* Sort the vector to find the median. Note that though this takes O(nlogn) time, it can be done in O(n) using Quick Select Algorithm.*/
        
      int median = nums[nums.size()/2]; // Works for both odd and even number of elements
      int res = 0;
      for(int i=0;i<nums.size();i++)
      {
          res += abs(nums[i]-median); // How far is each element from median
      }
      return res;
    }};

  • 1
    L

    You can just the nth_element() function to cut the time complexity to O(n)


  • 0

    Agreed. Sorting isn't required in this case.


  • 0
    K

    int median = nums[nums.size()/2];
    why works for both odd and even number of elements


Log in to reply
 

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