题解 | 明明的随机数

package main

import (
	"fmt"
)

// 巧妙解法：位图 + 位运算优化
// 时间复杂度：O(n + k)，空间复杂度：O(k/32)
// 其中k=500为数据范围，n为输入数量
func main() {
	var n int
	fmt.Scanln(&n)

	// 使用位图存储数字存在状态
	// 每个uint32可以存储32个数字的状态，500个数字需要16个uint32
	const maxNum = 500
	bitmap := make([]uint32, (maxNum+31)/32) // 向上取整

	// 读取数字并在位图中标记
	for i := 0; i < n; i++ {
		var num int
		fmt.Scanln(&num)
		setBit(bitmap, num)
	}

	// 遍历位图输出已存在的数字
	outputSortedUniqueNumbers(bitmap, maxNum)
}

// 设置位图中对应位置为1（内联优化）
func setBit(bitmap []uint32, num int) {
	wordIndex := num >> 5 // 等价于 num / 32，位运算更快
	bitOffset := num & 31 // 等价于 num % 32，位运算更快
	bitmap[wordIndex] |= 1 << bitOffset
}

// 检查位图中指定位置是否为1（内联优化）
func getBit(bitmap []uint32, num int) bool {
	wordIndex := num >> 5
	bitOffset := num & 31
	return (bitmap[wordIndex] & (1 << bitOffset)) != 0
}

// 输出排序后的唯一数字（利用位图天然有序的特性）
func outputSortedUniqueNumbers(bitmap []uint32, maxNum int) {
	for num := 1; num <= maxNum; num++ {
		if getBit(bitmap, num) {
			fmt.Println(num)
		}
	}
}

// 更巧妙的进阶版本：使用位运算技巧批量处理
func advancedBitmapSolution() {
	var n int
	fmt.Scanln(&n)

	// 使用计数排序的思想，但用位图优化空间
	const maxNum = 500
	bitmap := make([]uint64, (maxNum+63)/64) // 使用uint64提高效率

	// 批量读取和处理
	nums := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scanln(&nums[i])
		setBit64(bitmap, nums[i])
	}

	// 使用位运算技巧快速查找和输出
	for i := 0; i < len(bitmap); i++ {
		word := bitmap[i]
		baseNum := i * 64

		// 使用位运算快速找到所有设置的位
		for word != 0 {
			// 找到最低位的1的位置
			trailingZeros := countTrailingZeros(word)
			num := baseNum + trailingZeros + 1

			if num <= maxNum {
				fmt.Println(num)
			}

			// 清除最低位的1
			word &= word - 1
		}
	}
}

// 设置64位位图中对应位置
func setBit64(bitmap []uint64, num int) {
	wordIndex := num >> 6 // num / 64
	bitOffset := num & 63 // num % 64
	bitmap[wordIndex] |= 1 << bitOffset
}

// 计算尾随零的个数（使用内置函数或位运算技巧）
func countTrailingZeros(x uint64) int {
	if x == 0 {
		return 64
	}
	count := 0
	for (x & 1) == 0 {
		count++
		x >>= 1
	}
	return count
}

// 面试官最爱的一行流解法（展示函数式编程思维）
func oneLineSolution() {
	// 虽然在Go中不太适用，但可以展示思维
	// 在其他语言中可以写成：
	// Arrays.stream(nums).distinct().sorted().forEach(System.out::println)
}

// 内存极限优化版本：流式处理
func memoryOptimizedSolution() {
	var n int
	fmt.Scanln(&n)

	// 只使用500位的位图，约63字节
	var bitmap [16]uint32 // 16 * 32 = 512 bits，覆盖1-500

	// 流式处理，边读边标记
	for i := 0; i < n; i++ {
		var num int
		fmt.Scanln(&num)
		if num >= 1 && num <= 500 {
			bitmap[num>>5] |= 1 << (num & 31)
		}
	}

	// 输出结果
	for num := 1; num <= 500; num++ {
		if (bitmap[num>>5] & (1 << (num & 31))) != 0 {
			fmt.Println(num)
		}
	}
}

解题思路

算法分析

这道题的核心是去重排序。由于数据范围限制在1-500，我们可以设计多种高效算法：

1. 朴素解法：排序后去重，时间复杂度O(n log n)
2. 位图算法：利用数据范围小的特点，时间复杂度O(n + k)
3. 布尔数组：类似位图但更直观，空间换时间
4. 计数排序：统计每个数字出现次数，天然去重

多种解法对比

graph TD
    A[输入数据] --> B{选择算法}
    B -->|数据量大| C[排序+去重 O(n log n)]
    B -->|数据范围小| D[位图算法 O(n + k)]
    B -->|空间充足| E[布尔数组 O(n + k)]
    B -->|需要统计| F[计数排序 O(n + k)]
    
    C --> G[sort.Ints + 去重遍历]
    D --> H[位运算操作]
    E --> I[布尔数组标记]
    F --> J[计数数组统计]
    
    G --> K[输出结果]
    H --> K
    I --> K
    J --> K

位图算法详解

flowchart TD
    A[初始化位图bitmap] --> B[读取数字]
    B --> C[设置对应位为1]
    C --> D{还有数字?}
    D -->|是| B
    D -->|否| E[遍历位图]
    E --> F{当前位是否为1?}
    F -->|是| G[输出对应数字]
    F -->|否| H[跳过]
    G --> I{还有位?}
    H --> I
    I -->|是| E
    I -->|否| J[结束]

计数排序优化

graph LR
    A[数字1] --> B[count[1]++]
    C[数字2] --> D[count[2]++]
    E[数字2] --> D
    F[遍历count数组] --> G[输出非零位置]

时间复杂度对比

其中k为数据范围，本题k=500

位运算技巧

graph TD
    A[数字x] --> B[字节位置: x/32]
    A --> C[位偏移: x%32]
    B --> D[bitmap[x/32]]
    C --> E[1 << (x%32)]
    D --> F[位或运算设置位]
    E --> F
    F --> G[bitmap[x/32] |= (1 << (x%32))]

空间优化技巧

1. 位图压缩：用uint32数组，每个元素存储32个数字的存在状态
2. 稀疏数组：如果数据稀疏，可以用map存储
3. 流式处理：边读边处理，不存储所有数据

实际应用场景

1. 大数据去重：处理海量重复数据
2. 布隆过滤器：快速判断元素是否存在
3. 数据库索引：位图索引在数据库中的应用
4. 缓存优化：内存中快速查找和去重

这个问题虽然简单，但可以展示多种算法思维和优化技巧，特别是利用数据范围特点进行空间换时间的优化思想。