Why my solution is much more slower than others?


  • 0
    Z
    class Solution {
    public:
        int minMoves2(vector<int>& nums) {
            int len = nums.size(), f = 0, r = len - 1, mid = len >> 1, res = 0;
            for(;;) {
                int val = nums[f], front = f, rear = r;
                while(front < rear) {
                    while(nums[rear] >= val && front < rear) {
                        --rear;
                    }
                    nums[front] = nums[rear];
                    while(nums[front] <= val && front < rear) {
                        ++front;
                    }
                    nums[rear] = nums[front];
                }
                nums[front] = val;
                if(front > mid) {
                    r = front - 1;
                } 
                else if(front < mid){
                    f = front + 1;
                } 
                else {
                    for(int i = 0; i < mid; ++i) {
                        res += val - nums[i];
                    } 
                    for(int i = mid + 1; i < len; ++i) {
                        res += nums[i] - val;
                    }
                    return res;
                }
            }
            return res;
        }
    };
    

    I thought it should be faster than these solutions which use sort, but the running time is 139 ms;


Log in to reply
 

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