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

• 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;
}``````

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

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