C++ Solution - Easy to Understand

  • 1
    class Solution {
    int minMoves2(vector<int>& nums) {
      /* 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

    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

    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.