Golang | Leetcode Golang题解之第324题摆动排序II

题目：

题解：

func wiggleSort(nums []int) {n := len(nums)x := (n + 1) / 2target := quickSelect(nums, x-1)transAddress := func(i int) int { return (2*n - 2*i - 1) % (n | 1) }for k, i, j := 0, 0, n-1; k <= j; k++ {tk := transAddress(k)if nums[tk] > target {for j > k && nums[transAddress(j)] > target {j--}tj := transAddress(j)nums[tk], nums[tj] = nums[tj], nums[tk]j--}if nums[tk] < target {ti := transAddress(i)nums[tk], nums[ti] = nums[ti], nums[tk]i++}}
}func quickSelect(a []int, k int) int {rand.Seed(time.Now().UnixNano())rand.Shuffle(len(a), func(i, j int) { a[i], a[j] = a[j], a[i] })for l, r := 0, len(a)-1; l < r; {pivot := a[l]i, j := l, r+1for {for i++; i < r && a[i] < pivot; i++ {}for j--; j > l && a[j] > pivot; j-- {}if i >= j {break}a[i], a[j] = a[j], a[i]}a[l], a[j] = a[j], pivotif j == k {break} else if j < k {l = j + 1} else {r = j - 1}}return a[k]
}