https://leetcode.com/problems/wiggle-sort/
Wiggle Sort
Total Accepted: 1570 Total Submissions: 3651 Difficulty: Medium
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].
Code:
class Solution(object):
def wiggleSort(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
for x in xrange(1, len(nums), 2):
if x < len(nums)-1 and nums[x+1] > nums[x]:
nums[x], nums[x+1] = nums[x+1], nums[x]
if nums[x] < nums[x-1]:
nums[x], nums[x-1] = nums[x-1], nums[x]
Idea:
You start from every odd index of x, if nums[x+1] > nums[x], you exchange them. At the moment after the exchange, nums[x] > nums[x+1] for sure. Now, if you also find that nums[x-1] > nums[x], nums[x-1] must already be larger than nums[x+1]. So you are safe to exchange nums[x-1] and nums[x] to meet nums[x-1] <= nums[x] >= nums[x+1] without any potential to break the inequality.