文档章节

LeetCode 41. 缺失的第一个正数

猪迪
 猪迪
发布于 2018/05/25 11:16
字数 219
阅读 204
收藏 0

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

示例 1:

输入: [1,2,0]
输出: 3

示例 2:

输入: [3,4,-1,1]
输出: 2

示例 3:

输入: [7,8,9,11,12]
输出: 1

说明:

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

填充一个元素0,
首先排除掉小于0和超过数组大小的元素,将它们统一赋值为0;
利用i!=nums[j] =====> nums[i]!=nums[nums[j]%n](操作nums[nums[j]%n]取负,倍增)得到不在nums中的最小正整数

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        nums.push_back(0);
        int n=nums.size();
        
        for(int i=0;i<n;i++){
            if(nums[i]<=0||nums[i]>=n) nums[i]=0;
        }
        
        for(int i=0;i<n;i++){
            nums[nums[i]%n]+=n;   
        }
        
        for(int i=1;i<n;i++){
            if(nums[i]/n==0) return i;
        }
        return n;
    }
};

 

© 著作权归作者所有

共有 人打赏支持
上一篇: bash 词频统计
下一篇: scala泛函编程(1)
猪迪
粉丝 6
博文 134
码字总数 180528
作品 0
海淀
程序员
私信 提问
LeetCode 41 First Missing Positive(丢失的第一个正数)

版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/52435582 翻译 给定一个未排序的整型数组,找出第一个丢失的正...

nomasp
2016/09/04
0
0
LeetCode算法题-Find All Numbers Disappeared in an Array(Java实现)

这是悦乐书的第232次更新,第245篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第99题(顺位题号是448)。给定一个整数数组,其中1≤a[i]≤n(n =数组的大小),一些元素出现...

小川94
01/16
0
0
雪花算法-snowflake

snowflake 算法 snowflake 算法是 twitter 开源的分布式 id 生成算法,就是把一个 64 位的 long 型的 id,1 个bit是不用的,用其中的 41 bit 作为毫秒数,用 10 bit 作为工作机器 id,12 bi...

拐美人
01/02
0
0
[leetcode] Palindrome Number

Determine whether an integer is a palindrome. Do this without extra space. Some hints: Could negative integers be palindromes? (ie, -1) If you are thinking of converting the int......

jdflyfly
2014/06/24
0
0
剑指offer 41. 和为S的连续正数序列

原题 小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,...

dby_freedom
2018/11/20
0
0

没有更多内容

加载失败,请刷新页面

加载更多

VMware下centos7.x 用yum快速搭建LAMP平台

实验环境: [root@nmserver-7 html]# cat /etc/redhat-release CentOS release 7.3.1611 (AltArch) [root@nmserver-7 html]# uname -aLinux nmserver-7.test.com 3.10.0-514.el7.cent......

皇冠小丑
55分钟前
1
0
搜索引擎(Solr-索引详解)

时间字段类型特别说明 Solr中提供的时间字段类型( DatePointField, DateRangeField,废除的TrieDateField )是以时间毫秒数来存储时间的。 要求字段值以ISO-8601标准格式来表示时间:YYYY-MM...

这很耳东先生
今天
6
0
Java成神之路

1、基础篇 01、面向对象 → 什么是面向对象 面向对象、面向过程 面向对象的三大基本特征和五大基本原则 → 平台无关性 Java 如何实现的平台无关 JVM 还支持哪些语言(Kotlin、Groovy、JRuby...

asdf08442a
今天
3
0
dubbo源码分析-服务导出

简介 dubbo框架spring Schema扩展机制与Spring集成,在spring初始化时候加载dubbo的配置类。 dubbo服务导出的入口类是ServiceBean的onApplicationEvent方法 ServiceBean的继承关系如下 publ...

王桥修道院副院长
今天
2
0
QQ音乐的动效歌词是如何实践的?

本文由云+社区发表 作者:QQ音乐技术团队 一、 背景 1. 现状 歌词浏览已经成为音乐app的标配,展示和动画效果也基本上大同小异,主要是单行的逐字染色的卡拉OK效果和多行的滚动效果。当然,我...

腾讯云加社区
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部