如何在O(1)空间下将荷兰国旗排序数组重排为摆动顺序

给定一个已按荷兰国旗规则排序的数组：

• nums[:i] 中所有元素小于mid
• nums[i:j] 中所有元素等于mid
• nums[j:] 中所有元素大于mid

要求原地将其重排成摆动顺序：nums[0] < nums[1] > nums[2] < nums[3]...，题目保证存在有效解。

核心思路 #

结合你提到的Virtual Indexing技术，我们不需要像LeetCode 324那样先找中位数再做全局三路划分——因为数组已经是分好三个区域的，直接利用现有分区映射到摆动排序的目标位置即可：

• 摆动排序的核心要求是奇数位元素大于相邻偶数位，因此我们只需把大于mid的元素放到奇数位，小于mid的元素放到偶数位，等于mid的元素填充剩余空位即可。
• 虚拟索引映射的作用是将实际数组的索引转换为摆动排序的目标位置，通过在虚拟索引空间内调整元素位置，实现原地重排。

具体步骤 #

1. 确定关键参数：
   • 数组长度n，计算映射模数mod = n if n%2 ==1 else n+1（保证模数为奇数，统一奇偶长度的映射逻辑）
   • 直接从数组中取mid值（因为数组已按荷兰国旗排序，取第一个非重复的分界值即可）
2. 定义映射函数：map_idx(idx) = (2*idx +1) % mod，该函数将虚拟索引转换为实际数组的索引，确保大于mid的元素最终落在奇数位，小于mid的落在偶数位。
3. 三路调整元素位置：
   • 用三个指针在虚拟索引空间内操作：
     • left：下一个放置大于mid元素的虚拟索引位置
     • right：下一个放置小于mid元素的虚拟索引位置
     • current：当前遍历的虚拟索引位置
   • 遍历虚拟索引空间，根据当前位置对应实际元素的大小，交换到目标区域，直到所有元素归位。

示例验证 #

输入数组[1,1,2,2,3,3]：

• n=6，mod=7，映射函数为(2*idx+1)%7
• mid=2，i=2（第一个等于mid的索引），j=4（第一个大于mid的索引）
• 按步骤调整后，最终得到[2,3,1,3,1,2]，满足摆动排序要求。

Python实现代码 #

def wiggle_sort(nums):
    n = len(nums)
    if n <= 1:
        return
    
    # 从荷兰国旗排序的数组中获取mid值
    mid = nums[0]
    for num in nums:
        if num != mid:
            mid = num
            break
    # 处理全是相同元素的情况（题目保证有解，此情况直接返回）
    if all(x == mid for x in nums):
        return
    
    mod = n if n % 2 == 1 else n + 1
    
    def map_idx(idx):
        return (2 * idx + 1) % mod
    
    left = 0
    right = n - 1
    current = 0
    
    while current <= right:
        real_pos = map_idx(current)
        if nums[real_pos] > mid:
            # 交换到left对应的实际位置
            nums[map_idx(left)], nums[real_pos] = nums[real_pos], nums[map_idx(left)]
            left += 1
            current += 1
        elif nums[real_pos] < mid:
            # 交换到right对应的实际位置
            nums[map_idx(right)], nums[real_pos] = nums[real_pos], nums[map_idx(right)]
            right -= 1
        else:
            current += 1

# 测试示例
nums = [1,1,2,2,3,3]
wiggle_sort(nums)
print(nums)  # 输出: [2,3,1,3,1,2]

内容的提问来源于stack exchange，提问作者PkDrew