Problem:
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].
Solution 1: NOTE:
For example, given nums = [3, 5, 2, 1, 6, 4], one possible answer is [1, 6, 2, 5, 3, 4].
Solution 1: NOTE:
Can we do something without sorting?
- we just check the following constraint with every even indexed element, because we need to maintain the wiggle order
- on the even index and that will be fine:
- --if an even indexed element is smaller than the previous odd indexed element, swap them
- --if and even indexed element is smaller than the next odd indexed element, swap them
- O(n) time, and O(1) space
Solution 2:
No comments:
Post a Comment