Skip to content
Branch: master
Find file History
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
..
Failed to load latest commit information.
324. Wiggle Sort II.go
324. Wiggle Sort II_test.go
README.md

README.md

324. Wiggle Sort II

题目

Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]....

Example 1:

Input: nums = [1, 5, 1, 1, 6, 4]
Output: One possible answer is [1, 4, 1, 5, 1, 6].

Example 2:

Input: nums = [1, 3, 2, 2, 3, 1]
Output: One possible answer is [2, 3, 1, 3, 1, 2].

Note:

You may assume all input has valid answer.

Follow Up:

Can you do it in O(n) time and/or in-place with O(1) extra space?

题目大意

给定一个数组,要求给它进行“摆动排序”,“摆动排序”即:nums[0] < nums[1] > nums[2] < nums[3]...

解题思路

这一题最直接的方法是先排序,然后用 2 个指针,一个指向下标为 0 的位置,另一个指向下标为 n/2 的位置。最终的数组的奇数位从下标为 0 开始往后取,偶数位从下标为 n/2 中间位置开始往后取。这种方法时间复杂度为 O(n log n)。

题目要求用时间复杂度 O(n) 和 空间复杂度 O(1) 的方法解决。思路如下,先找到数组中间大小的数字,然后把数组分为 2 部分:

Index :       0   1   2   3   4   5
Small half:   M       S       S    
Large half:       L       L       L(M)

奇数位排中间数和小于中间数的数字,偶数位排大于中间数的数字和中间数。如果中间数字有多个,那么偶数位最后几位也是中间数,奇数位开头的前几位也是中间数。

举例,给定一个数组如下,中间数是 5 。有 2 个 5 。

13   6   5   5   4   2

         M
Step 1: 
Original idx: 0    1    2    3    4    5  
Mapped idx:   1    3    5    0    2    4 
Array:        13   6    5    5    4    2 
             Left
              i
                                      Right

nums[Mapped_idx[i]] = nums[1] = 6 > 5, 所以可以把 6 放在第 1 个奇数位的位置。left 和 i 同时右移。

Step 2: 
Original idx: 0    1    2    3    4    5  
Mapped idx:   1    3    5    0    2    4 
Array:        13   6    5    5    4    2 
                  Left
                   i
                                      Right

nums[3] = 5 = 5, 5 可以放在下标为 3 的位置,由于 5 已经和中间数相等了,所以只后移 i 。

Step 3: 
Original idx: 0    1    2    3    4    5  
Mapped idx:   1    3    5    0    2    4 
Array:        13   6    5    5    4    2 
                  Left
                        i
                                     Right

nums[5] = 2 < 5, 因为比中位数小,所以应该放在偶数位的最后 1 位。这里的例子而言,应该放在下标为 4 的位置上。交换 nums[Mapped_idx[i]] 和 nums[Mapped_idx[Right]],交换完成以后 right 向左移。

Step 4: 
Original idx: 0    1    2    3    4    5  
Mapped idx:   1    3    5    0    2    4 
Array:        13   6    5    5    2    4 
                  Left
                        i
                               Right

nums[5] = 4 < 5, 因为比中位数小,所以应该放在偶数位的当前倒数第一位。这里的例子而言,应该放在下标为 2 的位置上。交换 nums[Mapped_idx[i]] 和 nums[Mapped_idx[Right]],交换完成以后 right 向左移。

Step 5: 
Original idx: 0    1    2    3    4    5  
Mapped idx:   1    3    5    0    2    4 
Array:        13   6    4    5    2    5 
                  Left
                        i
                            Right

nums[5] = 5 = 5, 由于 5 已经和中间数相等了,所以只后移 i 。

Step 6: 
Original idx: 0    1    2    3    4    5  
Mapped idx:   1    3    5    0    2    4 
Array:        13   6    4    5    2    5 
                  Left
                             i
                            Right

nums[0] = 13 > 5, 由于 13 比中位数大,所以可以把 13 放在第 2 个奇数位的位置,并移动 left 和 i 。

Step Final: 
Original idx: 0    1    2    3    4    5  
Mapped idx:   1    3    5    0    2    4 
Array:        5    6    4    13   2    5 
                      Left
                                  i
                            Right

i > Right, 退出循环,最终摆动排序的结果是 5 6 4 13 2 5 。

具体时间见代码,时间复杂度 O(n) 和 空间复杂度 O(1)。

You can’t perform that action at this time.