324. Wiggle Sort II (Medium)

https://leetcode.com/problems/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?

Solutions

class Solution {

    // This problem is too complicated, do not try again

    public void wiggleSort(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }

        int len = nums.length;

        // tmp is a temporary memory used to scan out the medium
        int[] tmp = new int[len];

        System.arraycopy(nums, 0, tmp, 0, nums.length);

        // Sort out the medium by which the nums is divided into two relatively equal size
        // parts and the elements in left section is smaller than that in right section.
        int medium = partition(tmp, 0, len - 1, len / 2);

        int[] ans = new int[len];

        // This is critical
        Arrays.fill(ans, medium);

        // stands for even index slot
        int evenPtr = 0;

        // stands for odd index slot
        int oddPtr = 1;

        for (int i = 0; i < len; i++) {
            // every even index swap in a smaller element in the left section.
            if (nums[i] < medium) {
                ans[evenPtr] = nums[i];
                evenPtr += 2;
            }
            // every odd index swap in a larger element in the left section.
            else if (nums[i] > medium) {
                ans[oddPtr] = nums[i];
                oddPtr += 2;
            }
        }

        System.arraycopy(ans, 0, nums, 0, nums.length);
    }

    private int partition(int[] nums, int l, int r, int mid) {
        int left = l;
        int right = r;

        int midVal = nums[left];

        // Sort nums by descending order.
        // Only left == right it will jumps out of the loop
        while (left < right) {

            // if left >= right is the cause to jump out the loop, left = right
            while (left < right && nums[right] >= midVal) {
                right--;
            }

            nums[left] = nums[right];

            // if left >= right is the cause to jump out the loop, left = right
            while (left < right && nums[left] <= midVal) {
                left++;
            }

            nums[right] = nums[left];
        }

        if (left ==  mid) {
            return midVal;
        }

        if (left <  mid) {
            return partition(nums, left + 1, r,  mid);
        }

        // left > mid
        return partition(nums, l, right - 1,  mid);
    }
}

Incorrect Solutions

References

Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2019-12-03 11:01:18

results matching ""

    No results matching ""