0324. Wiggle Sort I I

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.

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

解题思路 #

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

``````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 。

代码 #

``````
package leetcode

import (
"sort"
)

// 解法一
func wiggleSort(nums []int) {
if len(nums) < 2 {
return
}
median := findKthLargest324(nums, (len(nums)+1)/2)
n, i, left, right := len(nums), 0, 0, len(nums)-1

for i <= right {
if nums[indexMap(i, n)] > median {
nums[indexMap(left, n)], nums[indexMap(i, n)] = nums[indexMap(i, n)], nums[indexMap(left, n)]
left++
i++
} else if nums[indexMap(i, n)] < median {
nums[indexMap(right, n)], nums[indexMap(i, n)] = nums[indexMap(i, n)], nums[indexMap(right, n)]
right--
} else {
i++
}
}
}

func indexMap(index, n int) int {
return (1 + 2*index) % (n | 1)
}

func findKthLargest324(nums []int, k int) int {
if len(nums) == 0 {
return 0
}
return selection324(nums, 0, len(nums)-1, len(nums)-k)
}

func selection324(arr []int, l, r, k int) int {
if l == r {
return arr[l]
}
p := partition324(arr, l, r)

if k == p {
return arr[p]
} else if k < p {
return selection324(arr, l, p-1, k)
} else {
return selection324(arr, p+1, r, k)
}
}

func partition324(a []int, lo, hi int) int {
pivot := a[hi]
i := lo - 1
for j := lo; j < hi; j++ {
if a[j] < pivot {
i++
a[j], a[i] = a[i], a[j]
}
}
a[i+1], a[hi] = a[hi], a[i+1]
return i + 1
}

// 解法二
func wiggleSort1(nums []int) {
if len(nums) < 2 {
return
}
array := make([]int, len(nums))
copy(array, nums)
sort.Ints(array)
n := len(nums)
left := (n+1)/2 - 1 // median index
right := n - 1      // largest value index
for i := 0; i < len(nums); i++ {
// copy large values on odd indexes
if i%2 == 1 {
nums[i] = array[right]
right--
} else { // copy values decremeting from median on even indexes
nums[i] = array[left]
left--
}
}
}

``````

Apr 8, 2023