leetcode280-- Wiggle Sort --Locked

leetcode280-- Wiggle Sort --Locked

题目

题目的意思是给定一个随机的数组,返回一个新的数组,满足

nums[0]<=nums[1]>=nums[2]<=nums[3]....即摆动排序

解决方法有两种,第一种最容易想了,即先把数组排一个序,然后把第三位和第二位换,第5位和第4位换。。。。

这种因为涉及到排序,所以是O(nlogn)的时间复杂度。

解决法二是根据奇偶性不同来看

如下


def WiggleSort(nums):
    ##最容易想到的就是先将nums排个序,然后把第三个和第二个互换,第五个和第4个互换一下

    nums.sort()
    for i in range(1, len(nums)-1, 2):
        #if i < len(nums)-1:
        nums[i], nums[i+1] = nums[i+1], nums[i]

    return nums


lst = [3,5,20,1,6,4,9,8,10]
lst2 = []
lst2[:] = lst

print(WiggleSort(lst))


def WiggleSort2(nums):

    ## i>=1
    ## 注意是和其前面的进行比较,不是后面的.
    ## 其实可以发现如果i是even的话会有 nums[i]<=nums[i-1]
    ## 如果i是odd的话 nums[i]>=nums[i+1]
    ## 如果不满足的话就交换他们 

    for i in range(1, len(nums)):
        if (i%2==0 and nums[i] > nums[i-1]) or (i%2==1 and nums[i]<nums[i-1]):
            nums[i], nums[i-1] = nums[i-1], nums[i]

        print(i, nums)
    return nums

print(WiggleSort2(lst2))

## 可能会担心当后面的交换的时候会影响到前面的,其实是不用的,比如拿前三个来讲吧

"""
刚开始是3<=5, 所以不用换,但是5<=20, 所以要换,因为这时候3<=20仍然是对的,所以不会影响前面的,
如果第三个数字是2的话,也不用到,而第4个是1, 1就要和2换,同样因为5>=2>=1,所以5>=1,不会影响前面的结果.
"""


这样用后面的一种方法的话,时间复杂度就会降到O(n)了.

打赏,谢谢~~

取消

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

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

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