算法 缺失的第一个正整数-(哈希)

牛客网: 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 here
    dict := make(map[int]int)
    for _, num := range(nums) {
        dict[num]++
    }
    x := 1
    for dict[x] > 0 {
        x++
    }
    return x
}

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

// go
 
package 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 here
    n := 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
}