324. Wiggle Sort II #
Problem #
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?
Problem Summary #
Given an array, it is required to “wiggle sort” it. “Wiggle sort” means: nums[0] < nums[1] > nums[2] < nums[3]…
Solution Approach #
The most direct method for this problem is to sort first, then use 2 pointers, one pointing to the position with index 0, and the other pointing to the position with index n/2. In the final array, the odd positions are taken backward starting from index 0, and the even positions are taken backward starting from the middle position with index n/2. The time complexity of this method is O(n log n).
The problem requires solving it with a method of time complexity O(n) and space complexity O(1). The idea is as follows: first find the middle-sized number in the array, then divide the array into 2 parts:
Index : 0 1 2 3 4 5
Small half: M S S
Large half: L L L(M)
The odd positions place the middle number and numbers smaller than the middle number, while the even positions place numbers larger than the middle number and the middle number. If there are multiple middle numbers, then the last few even positions are also the middle number, and the first few odd positions at the beginning are also the middle number.
For example, given an array as follows, the middle number is 5. There are 2 5s.
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, so 6 can be placed at the position of the 1st odd position. left and i both move right.
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 can be placed at the position with index 3. Since 5 is already equal to the middle number, only i is moved backward.
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. Since it is smaller than the median, it should be placed at the last even position. In this example, it should be placed at the position with index 4. Swap nums[Mapped_idx[i]] and nums[Mapped_idx[Right]]. After the swap is complete, right moves left.
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. Since it is smaller than the median, it should be placed at the current last even position. In this example, it should be placed at the position with index 2. Swap nums[Mapped_idx[i]] and nums[Mapped_idx[Right]]. After the swap is complete, right moves left.
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. Since 5 is already equal to the middle number, only i is moved backward.
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. Since 13 is greater than the median, 13 can be placed at the position of the 2nd odd position, and left and i are moved.
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, exit the loop. The final result of wiggle sort is 5 6 4 13 2 5.
See the code for the details. Time complexity is O(n) and space complexity is O(1).
Code #
package leetcode
import (
"sort"
)
// Solution one
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
}
// Solution two
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--
}
}
}
中文