最小正数
题目:给你一个未排序的整数数组,请你找出其中没有出现的最小的正整数。
解法
- 新申请和原来一样长数组,将原数组数据对应新数组的下标,将新数组该下标设置为1.如原[1,3,-1,4],则新数组为[1,0,1,1]。则最小数为2.
func firstMissingPositive(nums []int) int {
var lenth = len(nums)
tow := make([]int, lenth+1)
for _,v := range nums {
if v >= 1 && v <= lenth {
tow[v] = 1
}
}
for k,v := range tow{
if k >= 1 && v != 1{
return k
}
}
return lenth+1
}
- 将数组转为二进制储存。
func firstMissingPositive(nums []int) int {
var lenth = len(nums)
bitlen := lenth/64 + 2
tow := make([]uint64, bitlen)
for _,v := range nums {
if v >= 0 && v <= lenth {
bit := v%64
index := v/64
tow[index] = tow[index] | (1 << uint64(bit))
}
}
var flag uint64
flag = 2
niminumber := 0
for i := 1; i<=lenth+32; i++{
niminumber++
if (flag & tow[i/64]) == 0 {
break
}
flag <<= 1;
if flag == 0{
flag = 1
}
}
return niminumber
}
网友评论