美文网首页
11 - Hard - 摆动排序 II

11 - Hard - 摆动排序 II

作者: 1f872d1e3817 | 来源:发表于2018-07-09 21:02 被阅读0次

    给定一个无序的数组 nums,将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]... 的顺序。

    示例 1:

    输入: nums = [1, 5, 1, 1, 6, 4]
    输出: 一个可能的答案是 [1, 4, 1, 5, 1, 6]
    示例 2:

    输入: nums = [1, 3, 2, 2, 3, 1]
    输出: 一个可能的答案是 [2, 3, 1, 3, 1, 2]
    说明:
    你可以假设所有输入都会得到有效的结果。

    进阶:
    你能用 O(n) 时间复杂度和 / 或原地 O(1) 额外空间来实现吗?

    时间复杂度O(nlogn),空间复杂度O(n)

    class Solution:
        def wiggleSort(self, nums):
            """
            :type nums: List[int]
            :rtype: void Do not return anything, modify nums in-place instead.
            """
            temp = sorted(nums)
            if len(nums) % 2 == 0:
                small, big = temp[:len(nums)//2], temp[len(nums)//2:]
            else:
                small, big = temp[:len(nums)//2+1], temp[len(nums)//2+1:]
            left, right = len(small)-1, len(big)-1
            i = 0
            while left >= 0 or right >= 0:
                if i % 2 == 0:
                    nums[i] = small[left]
                    left -= 1
                else:
                    nums[i] = big[right]
                    right -= 1
                i += 1
    

    上面算法的简版

    时间复杂度O(nlogn),空间复杂度O(1) (表面上。。)

    class Solution(object):
        def wiggleSort(self, nums):
            nums.sort()
            med = (len(nums) - 1) / 2
            nums[::2], nums[1::2] = nums[med::-1], nums[:med:-1]
    
    https://leetcode.com/problems/wiggle-sort-ii/discuss/141314/avg-time-O(n)-space-O(1)-Python-solution
    

    相关文章

      网友评论

          本文标题:11 - Hard - 摆动排序 II

          本文链接:https://www.haomeiwen.com/subject/ykxxpftx.html