// 第 13 周 – 实践课练习的参考答案
// 运行：go run ./w13/exercises
package main

import (
	"fmt"
	"math/rand"
	"slices"
)

// E1. 降序归并排序
func mergeSortDesc(a []int) []int {
	if len(a) <= 1 {
		return a
	}
	mid := len(a) / 2
	l, r := mergeSortDesc(slices.Clone(a[:mid])), mergeSortDesc(slices.Clone(a[mid:]))
	res := make([]int, 0, len(a))
	i, j := 0, 0
	for i < len(l) && j < len(r) {
		if l[i] >= r[j] {
			res = append(res, l[i])
			i++
		} else {
			res = append(res, r[j])
			j++
		}
	}
	res = append(res, l[i:]...)
	return append(res, r[j:]...)
}

// E2. 按长度稳定排序（归并排序）
func sortByLength(a []string) []string {
	if len(a) <= 1 {
		return a
	}
	mid := len(a) / 2
	l, r := sortByLength(slices.Clone(a[:mid])), sortByLength(slices.Clone(a[mid:]))
	res := make([]string, 0, len(a))
	i, j := 0, 0
	for i < len(l) && j < len(r) {
		if len(l[i]) <= len(r[j]) {
			res = append(res, l[i])
			i++
		} else {
			res = append(res, r[j])
			j++
		}
	}
	res = append(res, l[i:]...)
	return append(res, r[j:]...)
}

// E3. 用 O(n log n) 求逆序对的个数
func countInversions(a []int) ([]int, int) {
	if len(a) <= 1 {
		return a, 0
	}
	mid := len(a) / 2
	l, cl := countInversions(slices.Clone(a[:mid]))
	r, cr := countInversions(slices.Clone(a[mid:]))
	res := make([]int, 0, len(a))
	c := cl + cr
	i, j := 0, 0
	for i < len(l) && j < len(r) {
		if l[i] <= r[j] {
			res = append(res, l[i])
			i++
		} else {
			res = append(res, r[j])
			j++
			c += len(l) - i
		}
	}
	res = append(res, l[i:]...)
	return append(res, r[j:]...), c
}

// E4. 快速选择：第 k 小的元素（从 0 开始）
func quickSelect(a []int, k int) int {
	rnd := rand.New(rand.NewSource(3))
	lo, hi := 0, len(a)-1
	for {
		r := lo + rnd.Intn(hi-lo+1)
		a[r], a[hi] = a[hi], a[r]
		pivot, i := a[hi], lo-1
		for j := lo; j < hi; j++ {
			if a[j] < pivot {
				i++
				a[i], a[j] = a[j], a[i]
			}
		}
		a[i+1], a[hi] = a[hi], a[i+1]
		p := i + 1
		switch {
		case p == k:
			return a[p]
		case k < p:
			hi = p - 1
		default:
			lo = p + 1
		}
	}
}

// E5. 荷兰国旗问题
func dutchFlag(a []int) {
	lo, mid, hi := 0, 0, len(a)-1
	for mid <= hi {
		switch a[mid] {
		case 0:
			a[lo], a[mid] = a[mid], a[lo]
			lo++
			mid++
		case 1:
			mid++
		default:
			a[hi], a[mid] = a[mid], a[hi]
			hi--
		}
	}
}

// E6. 两个有序切片的中位数
func medianOfTwo(x, y []int) float64 {
	n := len(x) + len(y)
	i, j, prev, cur := 0, 0, 0, 0
	for k := 0; k <= n/2; k++ {
		prev = cur
		if j >= len(y) || (i < len(x) && x[i] <= y[j]) {
			cur = x[i]
			i++
		} else {
			cur = y[j]
			j++
		}
	}
	if n%2 == 1 {
		return float64(cur)
	}
	return float64(prev+cur) / 2
}

func main() {
	fmt.Println("E1. descending:", mergeSortDesc([]int{5, 2, 8, 1, 9, 3}))
	fmt.Println("E2. by length (stable):", sortByLength([]string{"pear", "fig", "apple", "kiwi", "date", "plum"}))
	_, inv := countInversions([]int{5, 2, 8, 1, 9, 3})
	fmt.Println("E3. inversions [5 2 8 1 9 3]:", inv)
	q := []int{7, 2, 9, 4, 3, 8, 6}
	fmt.Println("E4. k=2:", quickSelect(slices.Clone(q), 2), ", median (k=3):", quickSelect(slices.Clone(q), 3))
	f := []int{2, 0, 1, 2, 1, 0, 0, 2, 1}
	dutchFlag(f)
	fmt.Println("E5. Dutch flag:", f)
	fmt.Println("E6. median([1 3 8], [2 4 9 10]) =", medianOfTwo([]int{1, 3, 8}, []int{2, 4, 9, 10}), ", ([1 2], [3 4]) =", medianOfTwo([]int{1, 2}, []int{3, 4}))
}