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].

解题方法

先sort的方法

遇到这种问题，如果没有思路就先sort一下，sort之后后面的数肯定比前面的大，所以<=的条件都满足。 而>=的条件可以通过将两个元素swap一下来满足。

不需要sort的方法

其实并不需要sort, 直接遍历，在遍历的过程中根据Index的奇偶，和相邻两个数的大小比较，来决定是否swap

Solution

先sort的方法

O(nlogn

class Solution(object):
    def wiggleSort(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        if not nums:
            return
        nums.sort()
        length = len(nums)
        p = 1
        while p < length:
            if p + 1 >= length:
                break
            tmp = nums[p+1]
            nums[p+1] = nums[p]
            nums[p] = tmp
            p += 2

不需要sort, 直接O(n)的做法

class Solution(object):
    def wiggleSort(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        if not nums:
            return
        length = len(nums)
        p = 0
        while p < length:
            if p + 1 >= length:
                break
            if p % 2 == 1:
                if nums[p] < nums[p+1]:
                    tmp = nums[p+1]
                    nums[p+1] = nums[p]
                    nums[p] = tmp
            else:
                if nums[p] > nums[p+1]:
                    tmp = nums[p+1]
                    nums[p+1] = nums[p]
                    nums[p] = tmp
            p += 1

Reference

• google面经
• greedy算法