203 - 324 摆动排序2

题目

给定一个无序的数组 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) 额外空间来实现吗？

解答

感觉是要把数组分成两部分，小的和大的，全部小的要小于全部大的。然后两两插入即可。

排序

https://leetcode.com/problems/wiggle-sort-ii/discuss/155764/Python-3-lines-simplest-solution-for-everyone-to-understand

class Solution:
    def wiggleSort(self, nums: List[int]) -> None:
        s = sorted(nums, reverse=True)
        nums[1::2], nums[::2] = s[:(len(s))//2], s[(len(s))//2:]

Runtime: 172 ms, faster than 88.36% of Python3 online submissions for Wiggle Sort II.

Memory Usage: 15.6 MB, less than 11.11% of Python3 online submissions for Wiggle Sort II.

相当于。。

class Solution:
    def wiggleSort(self, nums: List[int]) -> None:
        arr = sorted(nums)
        for i in range(1, len(nums), 2):
            nums[i] = arr.pop()
        for i in range(0, len(nums), 2):
            nums[i] = arr.pop()

Runtime: 184 ms, faster than 50.38% of Python3 online submissions for Wiggle Sort II.

Memory Usage: 15.5 MB, less than 11.11% of Python3 online submissions for Wiggle Sort II.

用骚操作反而时间复杂度更低😂😂

光头大佬的魔法代码

https://leetcode.com/problems/wiggle-sort-ii/discuss/77678/3-lines-Python-with-Explanation-Proof

class Solution:
    def wiggleSort(self, nums: List[int]) -> None:
        nums.sort()
        half = len(nums[::2])
        nums[::2], nums[1::2] = nums[:half][::-1], nums[half:][::-1]

Runtime: 172 ms, faster than 88.12% of Python3 online submissions for Wiggle Sort II.

Memory Usage: 15.6 MB, less than 11.11% of Python3 online submissions for Wiggle Sort II.

class Solution:
    def wiggleSort(self, nums: List[int]) -> None:
        nums.sort()
        half = len(nums[::2])-1
        nums[::2], nums[1::2] = nums[half::-1], nums[:half:-1]

Runtime: 172 ms, faster than 88.17% of Python3 online submissions for Wiggle Sort II.

Memory Usage: 15.6 MB, less than 11.11% of Python3 online submissions for Wiggle Sort II.

class Solution:
    def wiggleSort(self, nums: List[int]) -> None:
        for i, num in enumerate(sorted(nums, reverse=True)):
            nums[(1+2*i) % (len(nums) | 1)] = num

Runtime: 176 ms, faster than 74.05% of Python3 online submissions for Wiggle Sort II.

Memory Usage: 15.5 MB, less than 11.11% of Python3 online submissions for Wiggle Sort II.

虚拟指针

https://leetcode.com/problems/wiggle-sort-ii/discuss/77677/O(n)%2BO(1)-after-median-Virtual-Indexing

class Solution:
    def wiggleSort(self, nums: List[int]) -> None:
        import random
        n = len(nums)
        k = len(nums)//2
        if len(set(nums)) > 100:
            random.shuffle(nums)

            def partition(nums, left, right):
                i = left-1
                povit = nums[right]
                for j in range(left, right):
                    if nums[j] < povit:
                        i += 1
                        nums[i], nums[j] = nums[j], nums[i]
                nums[i+1], nums[right] = nums[right], nums[i+1]
                return i+1
            left, right = 0, len(nums)-1
            while left <= right:
                pi = partition(nums, left, right)
                if pi > k:
                    right = pi-1
                elif pi < k:
                    left = pi + 1
                else:
                    break
            i, j = 0, k-1
            while i <= j:
                if nums[i] == nums[k]:
                    nums[i], nums[j] = nums[j], nums[i]
                    j -= 1
                else:
                    i += 1
            i, j = k+1, n-1
            while i <= j:
                if nums[j] == nums[k]:
                    nums[i], nums[j] = nums[j], nums[i]
                    i += 1
                else:
                    j -= 1
        else:
            nums.sort()
        if n & 1 == 0:
            nums[::2], nums[1::2] = nums[:k][::-1], nums[k:][::-1]
        else:
            nums[::2], nums[1::2] = nums[:k+1][::-1], nums[k+1:][::-1]

Runtime: 176 ms, faster than 74.05% of Python3 online submissions for Wiggle Sort II.

Memory Usage: 15.6 MB, less than 11.11% of Python3 online submissions for Wiggle Sort II.