牛客网: BM53

题目: 无重复元素数组中未出现的最小的正整数

思路:

(1) 使用单独hash表记录每个元素出现的次数，从1开始递增查询出现次数直到次数为0停止返回

(2) 将原数组作为hash表使用，处理好负数与0，将绝对值在N范围内的每个元素的绝对值减1定位到数组相关的下标将值置反（因为每个元素可能已被其他元素置为负数，所以需要取绝对值），遍历数组值为正数对应的下标加1即为缺失的正整数(由无重复元素保证)。

代码:

(1) 新建hash表

// go 哈希package main/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param nums int整型一维数组 * @return int整型
*/
func minNumberDisappeared( nums []int ) int {// write code heredict := make(map[int]int)for _, num := range(nums) {dict[num]++}x := 1for dict[x] > 0 {x++}return x
}

(2) 使用原数组作为hash表

// gopackage main
// import "fmt"/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param nums int整型一维数组 * @return int整型
*/
func abs(x int) int {if x >= 0 {return x} else {return -x}
}func minNumberDisappeared( nums []int ) int {// write code heren := len(nums)if n < 3 {return 0}// 处理所有负数for i := 0; i < n; i++ {if nums[i] <= 0 {nums[i] = n + 1}}// 使用坐标为key, 存储存在的n以内的正整数for i := 0; i < n; i++ {if abs(nums[i]) <= n {nums[abs(nums[i])-1] = -nums[abs(nums[i])-1]}}// 遍历值还为正的下标即为缺失的最小正整数for i := 0; i < n; i++ {if nums[i] > 0 {return i + 1}}return n + 1
}