题解 | 数组中未出现的最小正整数

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {
	for {
		scanner := bufio.NewScanner(os.Stdin)

		// 设置大缓冲区，防止大输入时出错
		buf := make([]byte, 1024*1024) // 1MB
		scanner.Buffer(buf, 1024*1024)
		scanner.Split(bufio.ScanWords) // 按单词扫描（空格、换行等分隔）

		// 读取第一行：n
		scanner.Scan()
		n, _ := strconv.Atoi(scanner.Text())
		if n == 0 {
			break
		}
		arr := make([]int, n)
		for i := 0; i < n; i++ {
			scanner.Scan()
			arr[i], _ = strconv.Atoi(scanner.Text())
		}
		fmt.Println(process(arr))
	}
}
// func process(arr []int) int {
// 	n := len(arr)
// 	hash := make([]int, n)
// 	for i := 0; i < n; i++ {
// 		if arr[i] >= 1 && arr[i] <= n && hash[arr[i]-1] == 0 {
// 			hash[arr[i]-1] = arr[i]
// 		}
// 	}
// 	for i := 0; i < n; i++ {
// 		if hash[i] != i+1 {
// 			return i + 1
// 		}
// 	}
// 	return n + 1
// }

func process(arr []int) int {
	n := len(arr)
	for i := 0; i < n; i++ {
		// 原地哈希做法
		for arr[i] >= 1 && arr[i] <= n && arr[arr[i]-1] != arr[i] {
			j := arr[i] - 1
			arr[j], arr[i] = arr[i], arr[j]
		}
	}
	for i := 0; i < n; i++ {
		if arr[i] != i+1 {
			return i + 1
		}
	}
	return n + 1
}