Question

Formatted question description: https://leetcode.ca/all/280.html

 280	Wiggle Sort

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

 For example, given nums = [3, 5, 2, 1, 6, 4], one possible answer is [1, 6, 2, 5, 3, 4].

 @tag-array

Algorithm

When i is odd, nums[i] >= nums[i-1]

When i is an even number, nums[i] <= nums[i-1]

According to its parity, compare it with its corresponding condition, and if it doesn’t match, just swap the position with the previous number.

Code

Java

import java.util.Arrays;

public class Wiggle_Sort {


    public class Solution {

        public void wiggleSort(int[] nums) {
            if (nums.length <= 1) {
                return;
            }
            for (int i = 1; i < nums.length; ++i) {
                if (    (i % 2 == 1 && nums[i] < nums[i - 1])
                        || (i % 2 == 0 && nums[i] > nums[i - 1])
                    ) {

                    swap(nums, i, i - 1);
                }
            }
        }
    }

    public class Solution_NlogN {

        /*
            When i is odd, nums[i] >= nums[i-1]
            When i is an even number, nums[i] <= nums[i-1]
         */
        public void wiggleSort(int[] nums) {
            if (nums.length <= 1) {
                return;
            }
            Arrays.sort(nums);

            for (int i = 2; i < nums.length; i += 2) {
                swap(nums, i, i - 1);
            }

        }
    }

    public void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

}

// OJ: https://leetcode.com/problems/wiggle-sort/
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        for (int i = 1; i + 1 < nums.size(); i += 2) {
            swap(nums[i], nums[i + 1]);
        }
    }
};

'''
math prove:

example [3, 5, 2, 1]
when reaching 2, all good
then next, is 1, so here comes the question, will the number after 2 violating the wiggle rule?

answer is no.
when reaching 2:
* if [3, 5, 2, 10], so 10 is bigger than 2, then no swap needed according to the if () conditions
* if [3, 5, 2, 1], so previous round, guaranteed that 2 is smaller than 5. And, now a swap needed meaning the number is smaller than 2, i.e. must be smaller than 5, so wiggle rule is still good

'''
class Solution:
    def wiggleSort(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        for i in range(1, len(nums)):
            if (i % 2 == 1 and nums[i] < nums[i - 1]) or (
                i % 2 == 0 and nums[i] > nums[i - 1]
            ):
                nums[i], nums[i - 1] = nums[i - 1], nums[i]

############

import random


class Solution(object):
  def wiggleSort(self, nums):
    """
    :type nums: List[int]
    :rtype: void Do not return anything, modify nums in-place instead.
    """
    if len(nums) <= 2:
      nums.sort()
      return
    numscopy = nums + []
    mid = self.quickselect(0, len(nums) - 1, numscopy, len(nums) / 2 - 1)
    ans = [mid] * len(nums)
    print
    ans
    if len(nums) % 2 == 0:
      l = len(nums) - 2
      r = 1
      for i in range(0, len(nums)):
        if nums[i] < mid:
          ans[l] = nums[i]
          l -= 2
        elif nums[i] > mid:
          ans[r] = nums[i]
          r += 2
    else:
      print
      'here'
      l = 0
      r = len(nums) - 2
      for i in range(0, len(nums)):
        if nums[i] < mid:
          ans[l] = nums[i]
          l += 2
        elif nums[i] > mid:
          ans[r] = nums[i]
          r -= 2

    for i in range(0, len(nums)):
      nums[i] = ans[i]

  def quickselect(self, start, end, A, k):
    if start == end:
      return A[start]

    mid = self.partition(start, end, A)

    if mid == k:
      return A[k]
    elif mid > k:
      return self.quickselect(start, mid - 1, A, k)
    else:
      return self.quickselect(mid + 1, end, A, k)

  def partition(self, start, end, A):
    left, right = start, end
    pivot = A[left]
    while left < right:
      while left < right and A[right] <= pivot:
        right -= 1
      A[left] = A[right]
      while left < right and A[left] >= pivot:
        left += 1
      A[right] = A[left]
    A[left] = pivot
    return left

280 - Wiggle Sort

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions