Worst case O(n^2) time O(1) space java solution 12ms


  • 0
    W

    If the number of the duplicates is much smaller than n, then the running time is O(n).

    public void wiggleSort(int[] nums) {
        if(nums.length<=1) return;
        
        for(int i=0;i<nums.length-1;i++) {
            if(i%2==0 && nums[i]>nums[i+1]) {
                swap(nums,i,i+1);
            } else if( i%2==1 && nums[i]<nums[i+1]) {
                swap(nums,i,i+1);
            } else if(nums[i]==nums[i+1]) {
                int j=i-1;
                // if there is a duplicate, just search back to find if this 
                // duplicate number can swap with some number before it.
                while(j>=0) {
                    if(nums[i]==nums[j]) {
                        j--;
                        continue;
                    }
                    if((j!=0 && j%2==0 && nums[i]<nums[j-1] && nums[i]<nums[j+1]) 
                      || (j==0 && nums[i]<nums[1])) {
                        swap(nums,i,j);
                        i=i-2;
                        break;
                      }
                    else if(j%2==1 && nums[i]>nums[j-1] && nums[i]>nums[j+1]) {
                        swap(nums,i,j);
                        i=i-2;
                        break;
                    }
                    j--;
                }
                
                // if search back does not find any number to swap with it, search forward then.
                if(j<0) {
                    j=i+1;
                    while(j<nums.length && nums[j]==nums[j-1]) j++;
                    if(j==nums.length) return;
                    if((i%2==0 && nums[j]>nums[i]) || (i%2==1 && nums[j]<nums[i])) 
                        swap(nums,i+1,j);
                    else if((i%2==0 && nums[j]<nums[i]) || (i%2==1 && nums[j]>nums[i]))
                        swap(nums,i,j);
                }
            }
        }
    }
    
    public void swap(int[] n, int i, int j) {
        int tmp=n[i];
        n[i]=n[j];
        n[j]=tmp;
    }

  • 0
    T

    You can not handle[ 5,6,4,5,4,6,5,5].....


Log in to reply
 

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