package otherutils

import "math/rand"

// 从max个数中随机选择N个
func ReservoirSampling(n int, max int) []int {
	if n <= 0 || max <= 0 {
		return nil
	}

	// 先把候选数前N个放入数组中
	result := make([]int, 0, n)
	for i := 0; i < max && i < n; i += 1 {
		result = append(result, i)
	}
	if n >= max {
		return result
	}

	for i := n; i < max; i++ {
		// 从0到i（包括）中随机选择一个索引j
		j := rand.Intn(i + 1)
		// 如果j小于n，则用当前元素i替换result中的第j个元素
		if j < n {
			result[j] = i
		}
		// 当i足够大时，每个元素被选中的概率都接近1/n
	}

	return result
}