41. 缺失的第一个正数

enali 发布于2019-07-30 18:37 / 661人阅读

摘要：问题问题描述给定一个未排序的整数数组，找出其中没有出现的最小的正整数。原因就在于使用的内置的函数的复杂度超过的比如的复杂度就是。

问题 问题描述

给定一个未排序的整数数组，找出其中没有出现的最小的正整数。

说明

你的算法的时间复杂度应为O(n)，并且只能使用常数级别的空间。

解答

首先因为只能使用常数级别的空间，就不能再建新的O(n)级的list，set等。然后就想到将列表去重去除非正数排序，最后循环当nums[i]和(i+1)不等是输出。

class Solution:
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums = list(set([i for i in nums if i > 0]))
        nums.sort()
        for i in range(len(nums)):
            if nums[i] != i + 1:
                return i + 1
        return len(nums) + 1

但是这样写并不正确。原因就在于使用的Python内置的函数的复杂度超过的O(n), 比如sort()的复杂度就是O(nlogn)。详细资料可以参考Python内置函数时间复杂度

经过思考，只需要将列表中在列表长度范围内的正整数n移动到列表(n-1)的位置，然后再循环当nums[i]和(i+1)不等是输出。

class Solution:
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        k = len(nums)
        if k == 0:
            return 1
        for i in range(k):
            while 0 < nums[i] <= k and nums[i] != nums[nums[i] - 1]:
                a = nums[nums[i] - 1]
                nums[nums[i] - 1] = nums[i]
                nums[i] = a
        for i in range(k):
            if nums[i] != i + 1:
                return i+1
        return k + 1

云服务器 GPU云服务器事件 41 Discuz41 android41 mysql 5.0.41

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/42765.html

LeetCode 之 JavaScript 解答第41题 —— 缺失的第一个正数（First Mis

摘要：小鹿题目算法思路桶排序思想。再遍历数组，从下标开始判断该下标是否存放规定的数据，如果不是则该下标就是这组数据中缺失的最小正整数。桶排序还可以实现在一组数据中查找重复的数据。 Time：2019/4/6Title: First Missing PositiveDifficulty: DifficultyAuthor: 小鹿题目：First Missing Positive Give...

levius 2019-08-23 16:46 评论0 收藏0
LeetCode41.缺失的第一个正数 JavaScript

摘要：给定一个未排序的整数数组，找出其中没有出现的最小的正整数。示例输入输出示例输入输出示例输入输出答案参考给定一个未排序的整数数组，找出其中没有出现的最小的正整数。示例 1: 输入: [1,2,0]输出: 3 示例 2: 输入: [3,4,-1,1]输出: 2 示例 3: 输入: [7,8,9,11,12]输出: 1 答案参考： /** * @param {number[]} num...

ymyang 2019-08-23 15:17 评论0 收藏0
6-9月技术文章汇总

摘要：分布式的管理和当我在谈论架构时我在谈啥状态码详解无状态协议和请求支持哪些方法分层协议栈有哪些数据结构运用场景说说你常用的命令为什么要有包装类面向对象的特征是啥是啥有什么好处系统设计工程在线诊断系统设计与实现索引背后的数据结构及算法原理软技能 HTTP 【HTTP】分布式session的管理【HTTP】Cookie和Session 【HTTP】当我在谈论RestFul架构时我在谈啥？...

miya 2019-07-30 18:03 评论0 收藏0
雪花算法（01）介绍

摘要：雪花算法生成的最终结果其实就是一个类型的长整型数字，这是一个大前提算法所有的内容都是针对这个数字进行运算的。根据上面的理论可以开始学习雪花算法。针对每个公司，随着服务化演进，单个服务越来越多，数据库分的越来越细，有的时候一个业务需要分成好几个库，这时候自增主键或者序列之类的主键id生成方式已经不再满足需求，分布式系统中需要的是一个全局唯一的id生成规则。既然号称在全局分布式系统中唯一...

or0fun 2019-08-19 10:29 评论0 收藏0
十道简单算法题二【Java实现】

摘要：前言清明不小心就拖了两天没更了这是十道算法题的第二篇了上一篇回顾十道简单算法题最近在回顾以前使用写过的数据结构和算法的东西，发现自己的算法和数据结构是真的薄弱，现在用改写一下，重温一下。前言清明不小心就拖了两天没更了～～这是十道算法题的第二篇了～上一篇回顾：十道简单算法题最近在回顾以前使用C写过的数据结构和算法的东西，发现自己的算法和数据结构是真的薄弱，现在用Java改写一下，...

Pluser 2019-08-15 15:19 评论0 收藏0