美文网首页
最小正数

最小正数

作者: 147258_d8b2 | 来源:发表于2020-06-28 11:08 被阅读0次

最小正数

题目:给你一个未排序的整数数组,请你找出其中没有出现的最小的正整数。

解法

  1. 新申请和原来一样长数组,将原数组数据对应新数组的下标,将新数组该下标设置为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
}
  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
}

相关文章

  • 最小正数

    最小正数 题目:给你一个未排序的整数数组,请你找出其中没有出现的最小的正整数。 解法 新申请和原来一样长数组,将原...

  • 欧拉计划5(最小倍数)

    题目 最小倍数 2520是最小的能够被1到10整除的数。 最小的能够被1到20整除的正数是多少? 分析 最小都能够...

  • 欧拉计划5 (最小倍数)

    题目:2520是最小的能够被1到10整除的数。最小的能够被1到20整除的正数是多少? Java: python3:...

  • 2022-11-13 一道很有意思的不等式

    已知正数,满足,求的最小值 直接移项: 由已知可以得到两边都是正数,两边平方,得到: 这里就需要用到常用的一个操作...

  • 有理数加减

    正数加正数,负数加负数,正数加负数正数减负数,负数减正数负数减负数,正数减正数。 以上是有理数的加减 在同号时绝对...

  • 628-三个数的最大乘积

    两种情况,第一种为两负数一个正数,第二种为全是正数: 找到最大的三个数和最小的两个数,比较两种情况乘积,复杂度O(N)

  • Java 基本数据类型

    byte byte数据类型是8位、有符号整数;有符号指的是有正数和负数之分 最小值是-128(-2^7) 最大值是...

  • 刷Lintcode:丢失第一个正整数

    中等题 描述:给出一个无序的正数数组,找出其中没有出现的最小正整数。 样例 如果给出[1,2,0], return...

  • ARTS第四周20200613

    Algorithm 缺失的第一个正数 给你一个未排序的整数数组,请你找出其中没有出现的最小的正整数。 示例 1: ...

  • LeetCode 力扣 41. 缺失的第一个正数

    题目描述(困难难度) 给一串数字,找出缺失的最小正数。限制了时间复杂度为 O(n),空间复杂度为 O(1)。 解法...

网友评论

      本文标题:最小正数

      本文链接:https://www.haomeiwen.com/subject/tyyifktx.html