Use partition algorithm. Easy to understand. O(n) time O(n) space.


  • 1
    M
    public class Solution {
        public int partition(int[] arr, int beg, int end) {
            int pivot = arr[beg];
            end++;
            while (beg < end) {
                while (beg < end && arr[--end] > pivot);
                arr[beg] = arr[end];
                while (beg < end && arr[++beg] <= pivot);
                arr[end] = arr[beg];
            }
            arr[beg] = pivot;
            return beg;
        }
        
        private void swap(int[] arr, int a, int b) {
            int t = arr[a];
            arr[a] = arr[b];
            arr[b] = t;
        }
        
        public void wiggleSort(int[] nums) {
            int n = nums.length;
            int k = n / 2 - 1;
            if (n % 2 == 1) k++;
            int beg = 0, end = n-1;
            for (;;) {
                int t = partition(nums, beg, end);
                if (t == k) {
                    if (k+1 < n && nums[k] == nums[k+1]) {
                        int val = nums[k];
                        for (int j = 0, i = 0; j <= k; j++) {
                            if (nums[j] == val) swap(nums, j, i++);
                        }
                        for (int j = n-1, i = n-1; j >= k+1; j--) {
                            if (nums[j] == val) swap(nums, j, i--);
                        }
                    }
                    break;
                } else if (t < k) {
                    beg = t+1;
                } else if (t > k) {
                    end = t-1;
                }
            }
            int[] arr = nums.clone();
            for (int i = 0; i < n; i++) {
                if (i % 2 == 0) {
                    nums[i] = arr[i/2];
                } else {
                    nums[i] = arr[i/2+k+1];
                }
            }
        }
    }
    

Log in to reply
 

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