324. Wiggle Sort II

Description

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

You may assume the input array always has a valid answer.

Example 1:

Input: nums = [1,5,1,1,6,4]
Output: [1,6,1,5,1,4]
Explanation: [1,4,1,5,1,6] is also accepted.

Example 2:

Input: nums = [1,3,2,2,3,1]
Output: [2,3,1,3,1,2]

Constraints:

1 <= nums.length <= 5 * 10⁴
0 <= nums[i] <= 5000
It is guaranteed that there will be an answer for the given input nums.

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

Solutions

Solution 1

Sort the array first, and then make adjustments.

The adjustment method is to find the number in the middle of the array, which is equivalent to dividing the ordered array into two parts from the middle.

Then take one from the end of the first half, and go one from the end of the second half, so that the first number is less than the second number.

Then take the second to last from the first half and take the second to last from the second half. This ensures that the second number is greater than the third number and the third number is less than the fourth number.

And so on until all of them are processed.

Solution 2

This implementation uses sorting. It traverses the relevant values and updates its state as each value is processed. Ordering the data first makes the subsequent comparisons deterministic. After all required states have been considered, the maintained result is returned.

class Solution {
    public void wiggleSort(int[] nums) {
        int[] arr = nums.clone();
        Arrays.sort(arr);
        int n = nums.length;
        int i = (n - 1) >> 1, j = n - 1;
        for (int k = 0; k < n; ++k) {
            if (k % 2 == 0) {
                nums[k] = arr[i--];
            } else {
                nums[k] = arr[j--];
            }
        }
    }
}


// Solution 2
class Solution {
    public void wiggleSort(int[] nums) {
        int[] bucket = new int[5001];
        for (int v : nums) {
            ++bucket[v];
        }
        int n = nums.length;
        int j = 5000;
        for (int i = 1; i < n; i += 2) {
            while (bucket[j] == 0) {
                --j;
            }
            nums[i] = j;
            --bucket[j];
        }
        for (int i = 0; i < n; i += 2) {
            while (bucket[j] == 0) {
                --j;
            }
            nums[i] = j;
            --bucket[j];
        }
    }
}

class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        vector<int> arr = nums;
        sort(arr.begin(), arr.end());
        int n = nums.size();
        int i = (n - 1) >> 1, j = n - 1;
        for (int k = 0; k < n; ++k) {
            if (k % 2 == 0)
                nums[k] = arr[i--];
            else
                nums[k] = arr[j--];
        }
    }
};


// Solution 2
class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        vector<int> bucket(5001);
        for (int& v : nums) ++bucket[v];
        int n = nums.size();
        int j = 5000;
        for (int i = 1; i < n; i += 2) {
            while (bucket[j] == 0) --j;
            nums[i] = j;
            --bucket[j];
        }
        for (int i = 0; i < n; i += 2) {
            while (bucket[j] == 0) --j;
            nums[i] = j;
            --bucket[j];
        }
    }
};

'''
>>> nums = list(range(1,11))
>>> nums
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
>>> nums[::2]
[1, 3, 5, 7, 9]
>>> nums[1::2]
[2, 4, 6, 8, 10]
>>>
>>> mid = (len(nums) - 1) // 2
>>> mid
4
>>> nums[mid::-1]
[5, 4, 3, 2, 1]
>>> nums[:mid:-1]
[10, 9, 8, 7, 6]
>>>
>>> nums[::2], nums[1::2] = nums[mid::-1], nums[:mid:-1]
>>> nums
[5, 10, 4, 9, 3, 8, 2, 7, 1, 6]
>>>
'''
class Solution:
    def wiggleSort(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        nums.sort()
        mid = (n - 1) // 2
        nums[::2], nums[1::2] = nums[mid::-1], nums[:mid:-1]

        # better to have descending list, below having error
        #   input: [4,5,5,6], below line output: [4,5,5,6]
        # nums[::2], nums[1::2] = nums[:mid+1:1], nums[mid+1::1]
        '''
        >>> nums=[4,5,5,6]
        >>> mid = (len(nums) - 1) // 2
        >>>
        >>> nums[::2]
        [4, 5]
        >>> nums[1::2]
        [5, 6]
        >>> nums[mid::-1]
        [5, 4]
        >>> nums[:mid:-1]
        [6, 5]
        >>> nums[::2], nums[1::2] = nums[mid::-1], nums[:mid:-1]
        >>> nums
        [5, 6, 4, 5]
        '''
class Solution: # extra space
    def wiggleSort(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        arr = sorted(nums) # extra O(N) space
        n = len(arr)
        i, j = (n - 1) >> 1, n - 1
        for k in range(n):
            if k % 2 == 0:
                nums[k] = arr[i]
                i -= 1
            else:
                nums[k] = arr[j]
                j -= 1

class Solution: # quicksort, without full sort
    def wiggleSort(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        if n <= 1:
            return
        
        mid = self.findKthLargest(nums, (n + 1) // 2)
        
        def idx(i):
            return (2 * i + 1) % (n | 1)
        
        i, j, k = 0, 0, n - 1
        while j <= k:
            if nums[idx(j)] > mid:
                nums[idx(i)], nums[idx(j)] = nums[idx(j)], nums[idx(i)]
                i += 1
                j += 1
            elif nums[idx(j)] < mid:
                nums[idx(j)], nums[idx(k)] = nums[idx(k)], nums[idx(j)]
                k -= 1
            else:
                j += 1
    
    def findKthLargest(self, nums: List[int], k: int) -> int:
        n = len(nums)
        left, right = 0, n - 1
        
        while True:
            pivotIdx = self.partition(nums, left, right)
            if pivotIdx == k - 1:
                return nums[pivotIdx]
            elif pivotIdx < k - 1:
                left = pivotIdx + 1
            else:
                right = pivotIdx - 1
    
    def partition(self, nums, left, right):
        pivot = nums[left]
        l, r = left + 1, right
        
        while l <= r:
            if nums[l] < pivot and nums[r] > pivot:
                nums[l], nums[r] = nums[r], nums[l]
                l += 1
                r -= 1
            elif nums[l] >= pivot:
                l += 1
            else:
                r -= 1
        
        nums[left], nums[r] = nums[r], nums[left]
        return r


# Solution 2
class Solution:
    def wiggleSort(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        bucket = [0] * 5001
        for v in nums:
            bucket[v] += 1
        n = len(nums)
        j = 5000
        for i in range(1, n, 2):
            while bucket[j] == 0:
                j -= 1
            nums[i] = j
            bucket[j] -= 1
        for i in range(0, n, 2):
            while bucket[j] == 0:
                j -= 1
            nums[i] = j
            bucket[j] -= 1

func wiggleSort(nums []int) {
	n := len(nums)
	arr := make([]int, n)
	copy(arr, nums)
	sort.Ints(arr)
	i, j := (n-1)>>1, n-1
	for k := 0; k < n; k++ {
		if k%2 == 0 {
			nums[k] = arr[i]
			i--
		} else {
			nums[k] = arr[j]
			j--
		}
	}
}


// Solution 2
func wiggleSort(nums []int) {
	bucket := make([]int, 5001)
	for _, v := range nums {
		bucket[v]++
	}
	n, j := len(nums), 5000
	for i := 1; i < n; i += 2 {
		for bucket[j] == 0 {
			j--
		}
		nums[i] = j
		bucket[j]--
	}
	for i := 0; i < n; i += 2 {
		for bucket[j] == 0 {
			j--
		}
		nums[i] = j
		bucket[j]--
	}
}

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var wiggleSort = function (nums) {
    let bucket = new Array(5001).fill(0);
    for (const v of nums) {
        bucket[v]++;
    }
    const n = nums.length;
    let j = 5000;
    for (let i = 1; i < n; i += 2) {
        while (bucket[j] == 0) {
            --j;
        }
        nums[i] = j;
        --bucket[j];
    }
    for (let i = 0; i < n; i += 2) {
        while (bucket[j] == 0) {
            --j;
        }
        nums[i] = j;
        --bucket[j];
    }
};

324 - Wiggle Sort II

324. Wiggle Sort II

Description

Solutions

Solution 1

Solution 2

All Problems

All Solutions

Welcome to Subscribe On Youtube

324. Wiggle Sort II

Description

Solutions

Solution 1

Solution 2

All Problems

All Solutions