Welcome to Subscribe On Youtube

280. Wiggle Sort

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 = [3,5,2,1,6,4]
Output: [3,5,1,6,2,4]
Explanation: [1,6,2,5,3,4] is also accepted.

Example 2:

Input: nums = [6,6,5,6,3,8]
Output: [6,6,5,6,3,8]

 

Constraints:

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

 

Follow up: Could you solve the problem in O(n) time complexity?

Solutions

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.

• Java
• Python
• Go
• C++

• class Solution {
      public void wiggleSort(int[] nums) {
          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);
              }
          }
      }
  
      private void swap(int[] nums, int i, int j) {
          int t = nums[i];
          nums[i] = nums[j];
          nums[j] = t;
      }
  }
  

• '''
  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.
  
  in example, 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]
  
  ############
  
  class Solution: # sort list first
      def wiggleSort(self, nums: List[int]) -> None:
          nums.sort()  # Sort the list in ascending order
          n = len(nums)
          
          for i in range(1, n - 1, 2):
              nums[i], nums[i + 1] = nums[i + 1], nums[i]  # Swap adjacent elements
          
          """
          If the list has an odd length, the last element will be compared with the second-to-last element
          and swapped if necessary to form a wiggle sequence.
          """
          if n % 2 == 0 or nums[-1] < nums[-2]:
              nums[-1], nums[-2] = nums[-2], nums[-1]
  
  ############
  import random
  
  class Solution:
      def wiggleSort(self, nums: List[int]) -> None:
          """
          Do not return anything, modify nums in-place instead.
          """
          if len(nums) <= 1:
              return
          
          # Find the median using quickselect
          n = len(nums)
          mid = self.quickselect(nums, 0, n-1, (n-1)//2)
          
          # Create an empty array with the same length as nums
          ans = [None] * n
          
          # Assign the median to every other element
          i = 0
          j = n-1 if n % 2 == 1 else n-2
          for k in range(n):
              if nums[k] < mid:
                  ans[j] = nums[k]
                  j -= 2
              elif nums[k] > mid:
                  ans[i] = nums[k]
                  i += 2
              else:
                  ans[j+1] = mid
          
          # Copy the result back to nums
          nums[:] = ans
      
      def quickselect(self, nums, left, right, k):
          """
          Returns the k-th smallest element in nums[left:right+1].
          """
          if left == right:
              return nums[left]
          
          # Partition the subarray around a pivot element
          pivot_idx = self.partition(nums, left, right)
          
          # Recursively select on the left or right subarray
          if k == pivot_idx:
              return nums[k]
          elif k < pivot_idx:
              return self.quickselect(nums, left, pivot_idx-1, k)
          else:
              return self.quickselect(nums, pivot_idx+1, right, k)
      
      def partition(self, nums, left, right):
          """
          Partitions the subarray nums[left:right+1] using the first element as the pivot.
          Returns the final index of the pivot element.
          """
          pivot = nums[left]
          i, j = left+1, right
          while i <= j:
              if nums[i] <= pivot:
                  i += 1
              elif nums[j] > pivot:
                  j -= 1
              else:
                  nums[i], nums[j] = nums[j], nums[i]
          nums[left], nums[j] = nums[j], nums[left]
          return j
  
  

• func wiggleSort(nums []int) {
  	for i := 1; i < len(nums); i++ {
  		if (i%2 == 1 && nums[i] < nums[i-1]) || (i%2 == 0 && nums[i] > nums[i-1]) {
  			nums[i], nums[i-1] = nums[i-1], nums[i]
  		}
  	}
  }
  

• class Solution {
  public:
      void wiggleSort(vector<int>& nums) {
          for (int i = 1; i < nums.size(); ++i) {
              if ((i % 2 == 1 && nums[i] < nums[i - 1]) || (i % 2 == 0 && nums[i] > nums[i - 1])) {
                  swap(nums[i], nums[i - 1]);
              }
          }
      }
  };
  

All Problems

All Solutions