Skip to content

Latest commit

 

History

History
88 lines (56 loc) · 2.13 KB

0280._Wiggle_Sort.md

File metadata and controls

88 lines (56 loc) · 2.13 KB

280. Wiggle Sort

难度: Medium

刷题内容

原题连接

内容描述

Given an unsorted array nums, reorder it in-place such that nums[0] <= nums[1] >= nums[2] <= nums[3]....

Example:

Input: nums = [3,5,2,1,6,4]
Output: One possible answer is [3,5,1,6,2,4]

解题方案

思路 1 - 时间复杂度: O(NlgN)- 空间复杂度: O(N)******

想的是比如bubble sort或者任何简单的比较sort,只是放数字的时候是按这样的大小顺序放:

1, n, 2, n-1,3, n-2….

或者每个pass其实做两个sort,找出最大的和最小的。然后分别放在头尾。

这样的写法TLE:

class Solution(object):
    def wiggleSort(self, nums):  # 此法超时
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
    n = len(nums)
    for i in range(n):
        # small bubble sort
        if i % 2 == 0:
            for j in range(n - 1, i - 1, -1):
                if nums[j] > nums[j - 1]:
                    nums[j], nums[j - 1] = nums[j - 1], nums[j]
        else:
            for j in range(n - 1, i - 1, -1):
                if nums[j] < nums[j - 1]:
                    nums[j], nums[j - 1] = nums[j - 1], nums[j]

思路 2 - 时间复杂度: O(N)- 空间复杂度: O(1)******

但是貌似想复杂了,其实对于这个简单化,要求只有一个:

  1. 如果i是奇数,nums[i] >= nums[i - 1]
  2. 如果i是偶数,nums[i] <= nums[i - 1]

所以我们只要遍历一遍数组,把不符合的情况交换一下就行了。具体来说,如果nums[i] > nums[i - 1], 则交换以后肯定有nums[i] <= nums[i - 1]。

AC 代码

class Solution(object):
    def wiggleSort(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        for i in range(1, len(nums)):
            if (i & 1 == 0 and nums[i] > nums[i-1]) or (i & 1 != 0 and nums[i] < nums[i-1]):
                nums[i], nums[i-1] = nums[i-1], nums[i]