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


  • 1
    M
    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..


Log in to reply
 

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