My Java Solution Accepted O(NlogN) with space O(n), run time 7ms

  • 0

    Idea is very simple. If the array is already sorted, we may exactly know how to get one answer:
    first half small numbers would be allocated to odd index numbers and last half would be allocated to even numbers.
    My solution is as belows:

        public void wiggleSort(int[] nums) {
            Arrays.sort(nums); // you can use better sorting like quick sort, but best is time O(NlogN)
            int[] temp = new int[nums.length];
            int s = (nums.length + 1) >> 1, t = nums.length;
            for (int i = 0; i < nums.length; i++) {
                temp[i] = (i & 1) == 0 ?  nums[--s] : nums[--t] ;
            for (int i = 0; i < nums.length; i++)
                nums[i] = temp[i];

Log in to reply

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