[Leetcode][Python]41: First Missing Positive
2024-08-21 11:59:25
# -*- coding: utf8 -*-
'''
__author__ = 'dabay.wang@gmail.com' 41: First Missing Positive
https://oj.leetcode.com/problems/first-missing-positive/ Given an unsorted integer array, find the first missing positive integer.
For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.
Your algorithm should run in O(n) time and uses constant space. ===Comments by Dabay===
要求O(n)的时间,肯定不能常规排序,意思是只能扫描一次。
因为对空间有要求,所以只能在已经有的空间上做文章。 扫描的时候,当遇到正数,而且这个正数小于数组长度(因为如果大于数组长度,说明前面肯定缺少正数,同时也没有(无需)位置来存储它),
就把它交换到下标和它一样的位置上。
这样,扫描完成之后,从1的位置开始判断,如果位置k上存的数字不是k,这就是缺少的第一个正数。 这道题有三个需要注意的地方:
- 交换之后,下标不能移动,需要继续判断。
- 可能从1开始到最后都没有缺少的正数,此时下一个正数可能放在第一个位置上。
- 当数组长度为0时,直接返回1.
''' class Solution:
# @param A, a list of integers
# @return an integer
def firstMissingPositive(self, A):
if len(A) == 0:
return 1
i = 0
while i < len(A):
if A[i] > 0 and A[i] < len(A) and A[A[i]] != A[i]:
A[A[i]], A[i] = A[i], A[A[i]]
else:
i = i + 1
for x in xrange(1, len(A)):
if A[x] != x:
return x
else:
if A[0] == len(A):
return len(A) + 1
else:
return len(A) def main():
s = Solution()
print s.firstMissingPositive([3,4,-1,1]) if __name__ == "__main__":
import time
start = time.clock()
main()
print "%s sec" % (time.clock() - start)
最新文章
- 浅谈SOA
- ionic项目 环境搭建及基本操作
- Start with connect by prior 递归查询
- Dijkstra算法(二)之 C++详解
- Mysql学习笔记(九)索引查询优化
- WP8.1&;Win10幸运大转盘源码分享
- 解决mysql出现“the table is full”的问题
- HDU 4597 Play Game(记忆化搜索,深搜)
- exit和_exit的区别
- SQLLoader7(只导入数据文件的其中几行记录)
- <;经验杂谈>;C#生成条形码
- URL 规范 整理
- mac更新node,npm版本
- Android开发者的Anko使用指南(四)之Layouts
- python网络编程(四)
- openvas安装和基本使用
- C# ASP.NET MVC 配置允许跨域访问
- MAC EI Capitan上更新系统自带SVN版本号(关闭SIP方能sudo rm)
- 泡泡一分钟:Motion Planning for a Small Aerobatic Fixed-Wing Unmanned Aerial Vehicle
- [administrative][archlinux][clonezilla][disk cloning] 一块 windows 10 硬盘的备份
热门文章
- Android Studio 调试过程中快捷查看断点处变量值(Ctrl+Shift+I无效)?
- 报LinkageError的原因
- JavaEE Tutorials (30) - Duke综合案例研究示例
- toolkit,phonetextbox中实现用户按回车键会换行
- bzoj1633 [Usaco2007 Feb]The Cow Lexicon 牛的词典
- zedboard--Opencv的移植(十)
- html 表格中文字的背景色
- sql语句收集
- AudioManager详解(结合源代码)
- Jquery ui datepicker 设置日期范围,如只能隔3天