Wiggle Sort II

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

Example 1:

Input: nums = [1, 5, 1, 1, 6, 4]
Output: One possible answer is [1, 4, 1, 5, 1, 6].

Example 2:

Input: nums = [1, 3, 2, 2, 3, 1]
Output: 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?

class Solution {
    // O(NlogN) Time & O(N) Space Solution
    public void wiggleSort(int[] nums) {
        int[] copy = Arrays.copyOf(nums, nums.length);
        Arrays.sort(copy);

        int n = nums.length;
        int left = (n + 1) / 2 - 1; // median index
        int right = n - 1; // largest value index
        for (int i = 0; i < nums.length; i++) { // copy large values on odd indexes
            if (i % 2 == 1) {
                nums[i] = copy[right];
                right--;
            } else { // copy values decremeting from median on even indexes
                nums[i] = copy[left];
                left--;
            }
        }
    }

    // O(n) average time and O(1) space Solution
    public void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }

    public int findKthLargest(int[] A, int k) {
        k = A.length - k; // convert to index of k largest
        int left = 0, right = A.length - 1;
        while (left <= right) {
            // Choosing left index as pivot element
            int i = left;
            for (int j = left + 1; j <= right; j++)
                if (A[j] < A[left]) {
                    i++;
                    swap(A, j, i);
                }
            // 'i' will be the head of list of element < pivot
            swap(A, left, i);

            if (k < i)
                right = i - 1;
            else if (k > i)
                left = i + 1;
            else
                return A[i];
        }
        return -1; // k is invalid
    }

    public void wiggleSort(int[] nums) {
        int median = findKthLargest(nums, (nums.length + 1) / 2);
        int n = nums.length;

        int left = 0, i = 0, right = n - 1;

        while (i <= right) {
            if (nums[newIndex(i, n)] > median)
                swap(nums, newIndex(left++, n), newIndex(i++, n));
            else if (nums[newIndex(i, n)] < median)
                swap(nums, newIndex(right--, n), newIndex(i, n));
            else
                i++;
        }
    }

    // What n|1 does it that it gets the next odd number to n if it was even
    private int newIndex(int index, int n) {
        return (1 + 2 * index) % (n | 1);
    }
}