CodeTop_Microsoft324 摆动排序Ⅱ

摆动排序Ⅱ

题目

给你一个整数数组 nums，将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]… 的顺序。

你可以假设所有输入数组都可以得到满足题目要求的结果。

奇数index的数字大于左右的偶数index数字

示例 1：

1
2
3
输入：nums = [1,5,1,1,6,4]
输出：[1,6,1,5,1,4]
解释：[1,4,1,5,1,6] 同样是符合题目要求的结果，可以被判题程序接受。

示例 2：

1
2
输入：nums = [1,3,2,2,3,1]
输出：[2,3,1,3,1,2]

提示：

  • 1 <= nums.length <= 5 * 104
  • 0 <= nums[i] <= 5000
  • 题目数据保证，对于给定的输入 nums ，总能产生满足题目要求的结果

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

题解

解法一

排序+逆序穿插

首先排序数组，对于排序后的数组的前部分是必然小于等于数组的后部分，中间可能有相等的情况，只需要将数组后半部分插入奇数，前半部分插入偶数位置即可；但是要注意中间相等的部分，使用逆序穿插把中间位置的数字穿插放到两边。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def wiggleSort(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        Cnums = sorted(nums)
        n = len(nums)
        for i in range(1,len(nums),2): #奇数大于偶数位置 先放置奇数
            n -= 1
            nums[i] = Cnums[n]
        for i in range(0,len(nums),2): #后放置偶数 因为中间的数据一部分在数组头，一部分在数组尾部，所以中间出现相等的情况就不会影响
            n -= 1
            nums[i] = Cnums[n] 
        return nums

但是实际上不需要排序，因为只需要找到中位数即可，无需保证中位数的左右部分是顺序的。

  • 首先找到中位数，准确说是第k个数（使用快速排序法）
  • 使用三分法将数组分成三个部分小于中位数，等于中位数，大于中位数的部分
  • 逆序穿插

这样时间复杂度为O(logn)+O(n),即为O(N)

解法二

总体函数

1
2
3
4
5
6
7
8
9
def wiggleSort(nums):
    n = len(nums)
    if n<=1: return nums
    k = (n+1)//2-1
    mid_value = partition(nums, k, 0, n-1)
    three_way_partition(nums, mid_value)
    nums0 = nums.copy()
    for k in range(n):
        nums[k] = nums0[(n+1)//2-1-k//2] if (not k%2) else nums0[(n-1)-k//2]

寻找中位数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def partition(nums, k, start, end):
    key = nums[start]
    left, right = start, end
    # print('nums={}, start={}, end={}'.format(nums,start,end))
    # 循环中的不变量: left<right and nums[right]>=key and nums[left]<=key
    while left < right:
        while left < right and nums[right] >= key:
            right = right - 1
        if left < right: nums[left],nums[right] = nums[right],nums[left]
        while left < right and nums[left] <= key:
            left = left + 1
        if left < right: nums[left],nums[right] = nums[right],nums[left]

    if left == k:
        return nums[left]
    elif left > k:
        return partition(nums, k, start, left-1)
    else:
        return partition(nums, k, left+1, end)

三分法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#三分法实现 {左侧}<=value<={右侧} 为使得左右两侧长度近似
#我们取 value = nums的第(n+1)//2 个数 同排序方法中前半段的最后一个数字
#参数l, r是小于/大于value的左右下标边界, 即nums[k]<=value for k<=l,nums[k]>=value for k>=r
#参数 i 是当前遍历到的数字的下标 根据它和value的关系 我们确定 nums[i]是和 l 还是和 r 交换
#两个细节 【1】 while i<=r【2】 只有nums[i]<=value 交换之后i+=1
nums = [2,1,0,2,2,4] # mid=2
value = 2
def three_way_partition(nums, value):
    n=len(nums)
    l, r = 0, n-1
    i = 0
    #不能让i越过r 否则如果nums[l]<=nums[r]<nums[i] 会在下一次中让右侧更大的数字被换到左侧
    while i<=r: 
        if nums[i]<value:
            nums[l],nums[i]=nums[i],nums[l]
            l+=1
            i+=1
        elif nums[i]>value: #在这种情况下i不要移动 因为交换过来的数字nums[r]可能仍是>value
            nums[r],nums[i]=nums[i],nums[r]
            r-=1
        else:
            i+=1

逆序穿插

逆序之后的顺序: (n+1)//2-1 …1 || (n-1)…(n+1)//2
穿插之后的顺序: (n+1)//2-1, (n-1), (n+1)//2-1, (n-2),…, 1, (n+1)//2
(最后两个元素也可能是(n+1)//2，1）
k偶数：ind[0] - ind[k] = k//2 所以 ind[k] = ind[0]-k//2 = (n+1)//2-1-k//2
k奇数: ind[1] - ind[k] = k//2 所以 ind[k] = ind[1]-k//2 = (n-1)-k//2