深圳网站建设高端设计,个人养老金制度具体内容,温州网站设计定制,班级网站中个人简介怎么做牛客网: BM53
题目: 无重复元素数组中未出现的最小的正整数
思路:
(1) 使用单独hash表记录每个元素出现的次数#xff0c;从1开始递增查询出现次数直到次数为0停止返回
(2) 将原数组作为hash表使用#xff0c;处理好负数与0#xff0c;将绝对值在N范围内的每个元素的绝对…牛客网: 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
}
