Welcome to Subscribe On Youtube

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
    
    

All Problems

All Solutions