Java O(n) Time using QuickSelect


  • 18

    This solution relies on the fact that if we increment/decrement each element to the median of all the elements, the optimal number of moves is necessary. The median of all elements can be found in expected O(n) time using QuickSelect (or deterministic O(n) time using Median of Medians).

    public int minMoves2(int[] A) {
        int sum = 0, median = quickselect(A, A.length/2+1, 0, A.length-1);
        for (int i=0;i<A.length;i++) sum += Math.abs(A[i] - median);
        return sum;
    }
    
    public int quickselect(int[] A, int k, int start, int end) {
        int l = start, r = end, pivot = A[(l+r)/2];
        while (l<=r) {
            while (A[l] < pivot) l++;
            while (A[r] > pivot) r--;
            if (l>=r) break;
            swap(A, l++, r--);
        }
        if (l-start+1 > k) return quickselect(A, k, start, l-1);
        if (l-start+1 == k && l==r) return A[l];
        return quickselect(A, k-r+start-1, r+1, end);
    }
    
    public void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
    

  • 1
    L

    For readers who are not familiar with getting media from array, please refer to the popular posts in leetcode 215 Kth Largest Element in an Array.


  • 4
    P

    It is O(n^2) in the worst case.


  • 0
    A

    what if the length of the array is even? then the median should be the mean of the middle two numbers


  • 0
    F

    @aravindthangavel
    if n is even, then every number in [medianLeft, medianRight] is fine, so just pick one


  • 0
    F

    share some thought:

    this question is equal to find a number x such that sum is minimal.

    f(x):
    for (int num : nums) {
    value(i) = Math.abs(x - num);
    sum += value(i)
    }
    return sum;

    so consider function f(x), and sort the nums array. between consecutive number of array nums, we can see f(x) = E in [nums(i), nums(i + 1)].

    let nums(i) < median, if we decide let x go from nums(i) - delta to nums(i) + delta,
    value(t) t belongs to [0, i] will increase and value(t) t belongs to [len - i, len] will decrease with same value. and everything in (i, len - i) will decrease. so that why we choose median.


  • 0
    A

    @piyush121 i think if we randomize it, we will get better time that O(n^2)


  • 0
    Y

    @franklipolo great proof, but im a little confused about the sentence "we can see f(x) = E in [nums(i), nums(i + 1)].". Could you plz explain more in detail? What does this lead to? And what does E mean?


  • 0
    Y

    @franklipolo also, it is kinda hard to understand what if the len-i < i, and why value(t) t belongs to [len - i, len] will decrease the same?


  • 0
    S
    This post is deleted!

  • 0
    S

    Same idea for c++ version

        int minMoves2(vector<int>& nums) {
            int sum = 0;
            int median = findMedian(nums);
            for(int i=0; i < nums.size(); i++){
                sum += abs(nums[i]-median);
            }
            return sum;
        }
        int findMedian(vector<int>& nums){
            return findkthIntem(nums, nums.size()/2+1, 0, nums.size()-1);
        }
        int findkthIntem(vector<int>& nums, int k, int start, int end){
            int pivot = nums[end];
            int left = start;
            int right = end;
            while(true){
                while(left < right && nums[left] < pivot) left++;
                while(left < right && nums[right] >= pivot) right--;
                if(left==right)break;
                swap(nums[left],nums[right]);
            }
            swap(nums[left], nums[end]);
            if(k == left+1) return pivot;
            else if(k < left + 1) return findkthIntem(nums, k, start, left-1);
            else return findkthIntem(nums, k, left+1, end);
        }
    

  • 1
    J

    I think it is expected O(n) time only if the pivot is chosen randomly, as the input is not guaranteed to be uniformly distributed.


  • 0
    M

    C++ version of quickselect kth largest number:

    class Solution {
    public:
        int minMoves2(vector<int>& nums) {
            // O(n) sol by quickselect
            int median=findKthLargest(nums,0,nums.size()-1,nums.size()/2+1);
            int result=0;
            for(int num:nums) result+=abs(num-median);
            return result;
        }
    private:
        int partition(vector<int>& nums, int l, int r) {
            int pivot=nums[l+(r-l)/2];
            while(l<r) {
                while(l<r && nums[l]<pivot) l++;
                while(l<r && nums[r]>pivot) r--;
                if(nums[l]==nums[r]) l++;
                else swap(nums[l],nums[r]);
            }
            return r;
        }
        int findKthLargest(vector<int>& nums, int l, int r, int k) {
            int pos=partition(nums,l,r);
            if(k-1==pos) return nums[pos];
            else if(k-1<pos) return findKthLargest(nums,l,pos-1,k);
            else return findKthLargest(nums,pos+1,r,k);
        }
    };
    

Log in to reply
 

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