# Randomized solution (maybe O(n) ? and O(1))

• import java.util.Random;
public class Solution {
public void wiggleSort(int[] nums) {
if (nums == null) {
return;
}
int len = nums.length;
int tmp;
int j;
boolean odd;
boolean done = false;
if (len == 1) {
done = true;
}

while (!done) {
for (int i = 0; i < len - 1; i++) {
odd = !(i % 2 == 0);
if (!odd && nums[i] > nums[i + 1]
|| odd && nums[i] < nums[i + 1]) {
tmp = nums[i];
nums[i] = nums[i + 1];
nums[i + 1] = tmp;
}
if (nums[i] == nums[i + 1]) {
j = i + 2;
if (odd) {
while (j < len && nums[j] >= nums[i]) {
j++;
}
}
else {
while (j < len && nums[j] <= nums[i]) {
j++;
}
}
if (j >= len) {
shuffle(nums);
break;
}
tmp = nums[i + 1];
nums[i + 1] = nums[j];
nums[j] = tmp;
}
if (i == len - 2) {
done = true;
}
}
}
}

private void shuffle(int[] n) {
Random r = new Random();
int len = n.length;
int j;
int tmp;
for (int i = 0; i < len - 1; i++) {
j = r.nextInt(len - i - 1) + i + 1;
tmp = n[i];
n[i] = n[j];
n[j] = tmp;
}
}
}

The best case time complexity should be O(n). I don't know how to determine the worst..

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