share my C++ solution, almost certain O(n) time complexity


  • 0
    M
    class Solution {
    public:
        int PartitionAroundPivot(int left, int right, int pivot_idx, vector<int> &nums) {
            int pivot_val = nums[pivot_idx];
            int new_pivot_idx = left;
            swap(nums[pivot_idx], nums[right]);
            for (int i=left; i<right; i++) {
                if (nums[i] < pivot_val)
                    swap(nums[i], nums[new_pivot_idx++]);
            }
            swap(nums[right], nums[new_pivot_idx]);
            return new_pivot_idx;
        }
        
        int QuickSelect(vector<int> &nums, int k) {
            int left = 0, right = nums.size()-1;
            default_random_engine gen((random_device())());
            while (left <= right) {
                int pivot_idx = uniform_int_distribution<int>{left, right}(gen);
                int new_pivot_idx = PartitionAroundPivot(left, right, pivot_idx, nums);
                if (new_pivot_idx == k-1) {
                    return nums[k-1];
                }
                else if (new_pivot_idx > k-1) {
                    right = new_pivot_idx - 1;
                }
                else
                    left = new_pivot_idx + 1;
            }
        }
        
        int minMoves2(vector<int>& nums) {
            int ans = 0, median = QuickSelect(nums, (nums.size()+1)/2);
            for (int i=0; i<nums.size(); i++)
                ans += abs(nums[i]-median);
            return ans;
        }
    };
    

Log in to reply
 

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