DescriptionGiven an unsorted array nums, reorder it in-place such that:
nums \(\leqslant\) nums \(\geqslant\) nums \(\leqslant\) nums …
ExcampleGiven nums = [3,5,2,1,6,4], one possible answer is [1,6,2,5,3,4]
SolutionThis problem has a very straighforward solution. We start from the index 1 and check if the current number in that index satisfies the condition. If not, we swap that number and the the number before it.
Here is the code
The question is why this method works? In fact, we can prove it by induction.
class Solution: """ @param: nums: A list of integers @return: nothing """ def wiggleSort(self, nums): # write your code here for i in range(1, len(nums)): if i % 2 == 0: if nums[i] > nums[i - 1]: self.swap(nums, i, i-1) if i % 2 == 1: if nums[i] < nums[i-1]: self.swap(nums, i, i-1) def swap(self, nums, i, j): nums[i],nums[j] = nums[j], nums[i]
Proof. It is easy to check the approch works for n=1,2. for n = 3, we note that after two passes, the maximum number is at index 1, hence the array is wiggle sorted.
Now, assume the approach works for array of size less than or equal to n and we prove it also works for n+1. For simplicity, we will work on a concrete example and let n = 5.
The index starts from 1. When it arrives at index 4, we have
- \(a_5\) is the maximum number
- \(a_5\) is no the maximum number
In the first case, we are all good. In the second case, for
Now take a look at state of array when the index was 2. It is equivalent to start a new sort for array \([a_1,a_2,…,a_5]\) and the array \([a_0,a_1]\) is already sorted. Because we have a_1 be the largest number, when we starts sorting \([a_1,a_2,…,a_5]\), we will not change the position of a_1. Now we finish the proof by observing that size of array \([a_1,a_2,…,a_5]\) is n and by induction we know after the process is finished, \([a_1,a_2,…,a_5]\) will be wiggle sorted.
\( \square \)
----- END -----
©2019 - 2021 all rights reserved