[C++] Algorithm returns correct result on local machine but got Wrong Answer on the judge.


  • 0
    N

    Hi @1337c0d3r

    I have tested my following code on my local machine it always get correct result, but I am not sure why it always gets Wrong Answer on the judge?

    class Solution {
    public:
        
    
    // dutch flag partition
    void three_way_partition(vector<int> &nums, int pivot_value) {
        int l=-1,m=0,r=nums.size();
        while(m<r) {
            if(nums[r] < pivot_value)
                swap(nums[++l], nums[m++]);
            else if(nums[r] > pivot_value)
                swap(nums[--r], nums[m]);
            else
                ++m;
        }
    }
    
    // partition nums by value nums[pivot_index] and return the newest pivot index
    int partition(vector<int> &nums, int pivot_index, int left, int right) {
        swap(nums[right], nums[pivot_index]);
        
        int l=left-1, r=left;
        while(r < right) {
            if(nums[r]>=nums[right])
                r++;
            else
                swap(nums[++l],nums[r++]);
        }
        swap(nums[l+1], nums[right]);
        return l+1;
    }
    
    // find kth(zero based) smallest element in nums
    int select(vector<int> &nums, int k) {
        int left=0, right = (int)nums.size() - 1;
        
        while(left <= right) {
            default_random_engine gen((random_device())());
            uniform_int_distribution<int> dis(left, right);
            int pivot_index = dis(gen);
            int m = partition(nums, pivot_index, left, right);
            if(m == k)
                return nums[m];
            if(m < k)
                left = m+1;
            else
                right = m-1;
        }
        return -1;
    }
    
    void wiggleSort(vector<int>& nums) {
        int size = nums.size();
        if(size <=1)
            return;
        
        vector<int> tmp(size);
        int i=(size+1)/2 -1 ,j=size-1,k=0;
        int median = select(nums, i);
        three_way_partition(nums, median);
        while(k<size) {
            tmp[k] = k&1 ? nums[j--] : nums[i--];
            k++;
        }
        
        for(int u=0;u<size;u++)
            nums[u] = tmp[u];
    }
       
    };
    

  • 0

    @newtt See if this helps:
    https://leetcode.com/faq/#different-output

    Try to check for array out of bound access, as that would cause undefined behavior.


  • 0

    Of course you may get correct answer on local machine because you use random pivot. I think you may ignore the real hard part which is reordering from the semi-sorted array (small-mid-large).


  • 0
    N

    I think I found the issue I have a typo in the three_way_partition below is the correct algo that Accepted.

    '''
    while(m<r) {
    if(nums[m] < pivot_value)
    swap(nums[++l], nums[m++]);
    else if(nums[m] > pivot_value)
    swap(nums[--r], nums[m]);
    else
    ++m;
    }
    '''


Log in to reply
 

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