leetcode324-- Wiggle SortII

leetcode324-- Wiggle SortII

题目

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

Example 1:

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

Example 2:

Input: nums = [1, 3, 2, 2, 3, 1]
Output: One possible answer is [2, 3, 1, 3, 1, 2].

Note:
You may assume all input has valid answer.

Follow Up:
Can you do it in O(n) time and/or in-place with O(1) extra space?


解答是先排一个序,然后找到中间的那个位置,每次从两段的末尾往里面填,但是时间复杂度和空间复杂度不达标。。。


class Solution(object):
    def wiggleSort(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        
        # 这个相比第一个只改了一个等于号
        lst = []
        lst[:] = nums
        lst.sort()
        print(nums)
        print(lst)
        middle = (1+len(nums))/2
        end = len(nums)
        
        # 相当于是把数组分成两半,每次都取各自一半的最后一位,这样就能保证要求的序
        for i in range(len(nums)):
            if i&1:
                end -= 1
                nums[i]= lst[end]
            else:
                middle -= 1
                nums[i] = lst[middle]
        print(nums)
        

实际上就是先将数组排一个序,比如排好了之后 是1,2,3,4,5,6,7,8, 然后将数组从中间一分为二,分另是1,2,3,45,6,7,8, 然后新的数组接下来就是按这样的方式构造的每次都是从两个数组的后面开始取4,8,3,7,2,6,1,5.

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦