摆动排序

难度: Medium

Submission

运行时间: 16 ms

内存: 16.8 MB

class Solution:
    def wiggleSort(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        for i in range(n-1):
            if i % 2 == 0:
                if nums[i] > nums[i+1]:
                    nums[i],nums[i+1] = nums[i+1],nums[i]
            else:
                if nums[i] < nums[i+1]:
                    nums[i],nums[i+1] = nums[i+1],nums[i]

Explain

该题解的思路是通过一次遍历对数组进行就地修改，让相邻两个元素满足摆动排序的要求。具体来说，对于偶数下标 i，如果 nums[i] > nums[i+1]，就交换这两个元素；对于奇数下标 i，如果 nums[i] < nums[i+1]，就交换这两个元素。这样遍历修改一遍后，整个数组就满足了摆动排序的要求。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def wiggleSort(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        for i in range(n-1):
            # 对于偶数下标，如果当前元素大于下一个元素，交换它们
            if i % 2 == 0:
                if nums[i] > nums[i+1]:
                    nums[i], nums[i+1] = nums[i+1], nums[i]
            # 对于奇数下标，如果当前元素小于下一个元素，交换它们
            else:
                if nums[i] < nums[i+1]:
                    nums[i], nums[i+1] = nums[i+1], nums[i]

Explore

摆动排序要求数组中相邻的元素之间交替大于和小于。对于偶数下标的元素，题解中保证它不大于其后的元素（偶数下标的元素应该小于或等于其后的元素），而对于奇数下标的元素，则确保它不小于其后的元素（奇数下标的元素应该大于或等于其后的元素）。这种处理方式是为了确保数组在遍历一次后，满足摆动的条件，即偶数位置的元素应较小，奇数位置的元素应较大，从而形成一种“摆动”的模式。

通过对每一个元素进行条件判断并交换，算法确保了当前元素与其后一个元素满足摆动条件。但是，这种方法只保证了局部的正确性（即每对相邻元素），并没有全局的保障。理论上，通过这种一次遍历的方式，大多数情况下能够达成全局的摆动效果。然而，在某些特殊情况下（如多个相同的元素连续出现），可能在一次遍历后仍有不符合摆动排序的情况，需要进一步的验证或多次遍历来处理这种情况。

该算法对于数组长度是奇数或偶数处理方式相同，即通过遍历直至数组倒数第二个元素，并进行条件判断和交换。无论数组长度是奇数还是偶数，算法的基本逻辑不变。但是，不论数组的长度是奇数还是偶数，算法都可能在某些特定数据配置下无法完全达到全局的摆动效果，可能需要额外的遍历或其他技术手段来确保全局的摆动排序。

就地修改数组的方式意味着原数组的元素会被直接交换，从而节省了额外的空间开销。然而，这种方法可能会影响算法的稳定性，特别是在多线程环境下或者数组中包含有重复元素时。因为就地修改不提供额外的空间缓冲，一旦修改过程中发生错误（如程序崩溃），原始数据可能丢失或损坏。此外，就地修改可能会造成元素的原始顺序丢失，这在需要保持元素原始顺序的上下文中可能是不可接受的。