目录
324. 摆动排序 II Wiggle Sort ii 🌟🌟
324. 摆动排序 II Wiggle Sort ii
给你一个整数数组 nums，将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]... 的顺序。
你可以假设所有输入数组都可以得到满足题目要求的结果。
示例 1：
输入：nums = [1,5,1,1,6,4] 输出：[1,6,1,5,1,4] 解释：[1,4,1,5,1,6] 同样是符合题目要求的结果，可以被判题程序接受。
示例 2：
输入：nums = [1,3,2,2,3,1] 输出：[2,3,1,3,1,2]
提示：
1 <= nums.length <= 5 * 10^40 <= nums[i] <= 5000- 题目数据保证，对于给定的输入
nums，总能产生满足题目要求的结果
进阶：你能用 O(n) 时间复杂度和 / 或原地 O(1) 额外空间来实现吗？
代码：
package main
import "fmt"
func wiggleSort(nums []int) {
n := len(nums)
if n <= 1 {
return
}
heapSort(nums)
mid := n / 2
if n%2 == 0 {
mid--
}
temp := make([]int, n)
copy(temp, nums)
// 将较小的元素从末尾开始插入，较大的元素从中间位置开始插入
for i, j := 0, mid; i < n; i, j = i+2, j-1 {
nums[i] = temp[j]
}
for i, j := 1, n-1; i < n; i, j = i+2, j-1 {
nums[i] = temp[j]
}
}
// 堆排序
func heapSort(nums []int) {
n := len(nums)
// 建堆
for i := n/2 - 1; i >= 0; i-- {
adjustHeap(nums, i, n)
}
// 排序
for i := n - 1; i > 0; i-- {
nums[0], nums[i] = nums[i], nums[0]
adjustHeap(nums, 0, i)
}
}
// 调整堆
func adjustHeap(nums []int, root, n int) {
for {
child := 2*root + 1
if child >= n {
break
}
if child+1 < n && nums[child+1] > nums[child] {
child++
}
if nums[child] > nums[root] {
nums[child], nums[root] = nums[root], nums[child]
}
root = child
}
}
func main() {
nums1 := []int{1, 5, 1, 1, 6, 4}
wiggleSort(nums1)
fmt.Println(nums1)
nums2 := []int{1, 3, 2, 2, 3, 1}
wiggleSort(nums2)
fmt.Println(nums2)
}
输出：
[1 6 1 5 1 4]
[2 3 1 3 1 2]
280. 摆动排序 I Wiggle Sort i
给你一个没有排序的数组，请将原数组就地重新排列满足如下性质：nums[0] <= nums[1] >= nums[2] <= nums[3]......请写一个函数实现此排序功能。
示例 ：
输入：nums = [3, 5, 2, 1, 6, 4] 输出：[1, 6, 2, 5, 3, 4]
代码：
package main
import "fmt"
func wiggleSort(nums []int) {
n := len(nums)
findKthSmallest(nums, 0, n-1, n/2)
mid := nums[n/2]
i, j, k := 0, 0, n-1
for j <= k {
if nums[j] < mid {
nums[i], nums[j] = nums[j], nums[i]
i++
j++
} else if nums[j] > mid {
nums[j], nums[k] = nums[k], nums[j]
k--
} else {
j++
}
}
for i, j := 1, n-1; i < j; i, j = i+2, j-2 {
nums[i], nums[j] = nums[j], nums[i]
}
}
func findKthSmallest(nums []int, left, right, k int) {
if left == right {
return
}
pivot := partition(nums, left, right)
if k == pivot {
return
} else if k < pivot {
findKthSmallest(nums, left, pivot-1, k)
} else {
findKthSmallest(nums, pivot+1, right, k)
}
}
func partition(nums []int, left, right int) int {
pivot := nums[left]
for left < right {
for left < right && nums[right] >= pivot {
right--
}
nums[left] = nums[right]
for left < right && nums[left] <= pivot {
left++
}
nums[right] = nums[left]
}
nums[left] = pivot
return left
}
func main() {
nums := []int{3, 5, 2, 1, 6, 4}
wiggleSort(nums)
fmt.Println(nums)
}
输出：
[3 1 5 2 6 4]
🌟 每日一练刷题专栏 🌟
✨ 持续，努力奋斗做强刷题搬运工！
👍 点赞，你的认可是我坚持的动力！
🌟 收藏，你的青睐是我努力的方向！
✎ 评论，你的意见是我进步的财富！
☸ 主页：https://hannyang.blog.csdn.net/