LeetCode - Wiggle Sort II

WiggleSortII.java

// Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]....

// Example:
// (1) Given nums = [1, 5, 1, 1, 6, 4], one possible answer is [1, 4, 1, 5, 1, 6]. 
// (2) Given nums = [1, 3, 2, 2, 3, 1], one possible answer is [2, 3, 1, 3, 1, 2].

// Note:
// You may assume all input has valid answer.

// Follow Up:
// Can you do it in O(n) time and/or in-place with O(1) extra space?

// solution 1 --- O(nlogn) time complexity, O(n) space complexity
if(nums == null || nums.length < 2) return;
    Arrays.sort(nums);
    
    int mid = (nums.length + 1) / 2;
    int[] temp = new int[nums.length];
    
    int smallStart = mid - 1, largeStart = nums.length - 1;
    for(int i = 0; i < nums.length; i++){
        if(i % 2 == 0){
            temp[i] = nums[smallStart--];
        } else{
            temp[i] = nums[largeStart--];
        }
    }
    
    for(int n = 0; n < nums.length; n++) nums[n] = temp[n];
}

// solution 2 --- average O(n) time complexity, O(n) space complexity
public void wiggleSort(int[] nums) {
    if(nums == null || nums.length < 2) return;
    
    int mid = (nums.length + 1) / 2;
    int medium = findMedian(nums, mid);
    
    int[] temp = new int[nums.length];
    
    int s = 0, e = nums.length - 1;
    
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] < medium)
            temp[s++] = nums[i];
        else if (nums[i] > medium)
            temp[e--] = nums[i];
    }

    while (s < mid) temp[s++] = medium;
    while (e >= mid) temp[e--] = medium;
    
    int smallStart = mid - 1, largeStart = nums.length - 1;
    
    for(int i = 0; i < nums.length; i++){
        if(i % 2 == 0){
            nums[i] = temp[smallStart--];
        } else{
            nums[i] = temp[largeStart--];
        }
    }
    

}

// return the median of array
private int findMedian(int[] nums, int mid){
    int left = 0, right = nums.length - 1;
    while(true){
        int index = quickSelect(nums, left, right);
        if(index < mid){
            left = index + 1;
        } else if(index > mid){
            right = index - 1;
        } else break;
    }
    return nums[mid];
}

private int quickSelect(int[] nums, int low, int high){
    int left = low, right = high + 1;
    while(true){
        while(left < high && nums[++left] < nums[low]);
        while(low < right && nums[--right] > nums[low]);
        if(left >= right) break;
        swap(nums, left, right);
    }
    swap(nums, low, right);
    return right;
}

private void swap(int[] nums, int i, int j){
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}