leetcode-go/leetcode/medium/324.wiggle-sort-ii.go

func wiggleSort(nums []int) {
	n := len(nums)
	if n <= 1 {
		return
	}
	mid := quickSelect(nums, n/2)
	idx := func(i int) int {
		return (2*i + 1) % (n | 1)
	}
	l, m, r := 0, 0, n-1
	for m <= r {
		if mid < nums[idx(m)] {
			swap(&nums[idx(l)], &nums[idx(m)])
			l, m = l+1, m+1
		} else if nums[idx(m)] < mid {
			swap(&nums[idx(m)], &nums[idx(r)])
			r--
		} else {
			m++
		}
	}
}

func quickSelect(nums []int, k int) int {
	l, r := 0, len(nums)-1
	rand.Seed(time.Now().Unix())
	for l < r {
		swap(&nums[l], &nums[rand.Intn(r-l+1)+l])
		m := l
		for i := l + 1; i <= r; i++ {
			if nums[i] < nums[l] {
				m++
				swap(&nums[m], &nums[i])
			}
		}
		swap(&nums[l], &nums[m])
		if k <= m {
			r = m - 1
		}
		if m <= k {
			l = m + 1
		}
	}
	return nums[k]
}

func swap(x, y *int) {
	*x, *y = *y, *x
}