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