lintcode：First Missing Positive 丢失的第一个正整数
题目
给出一个无序的整数数组，找出其中没有出现的最小正整数。
如果给出 [1,2,0], return 3 如果给出 [3,4,-1,1], return 2
只允许时间复杂度O(n)的算法，并且只能使用常数级别的空间。
解题
感觉好像好像很复杂，通过率21%也是比较低的了。
找了一个很不好的方法
步骤：
1.先找出数组中正整数的最小值，Min
2.若Min>1 显然最小的不在数组中的正整数就是1
3.这里的都是最小值Min == 1的情况
对于这个情况，只需要判断 对最小的i， Min + i 是否在数组中的正整数部分，这里需要定义一个ArrayList存放正整数部分的数，方便判断Min+i是否在ArrayList中。最小的i对于的Min+i就是答案。
这里时间复杂度和空间复杂度都是O(N)
public class Solution {
/**
* @param A: an array of integers
* @return: an integer
*/
public int firstMissingPositive(int[] A) {
// write your code here
if(A.length ==0)
return 1;
// if(A.length ==1){
// if(A[0]<= 0)
// return 1;
// return A[0]+1;
// }
// 1.找到正数的最小值
// 2.最小值>1 return 1
// 3.最小值<0 return 1
// 4.最小值是1，最小值向上加 1 不存在的话就是答案
int Min = Integer.MAX_VALUE;
int MinInt = Integer.MAX_VALUE;
ArrayList<Integer> list = new ArrayList<Integer>();
for(int i=0;i< A.length;i++){
if(A[i]>0){
list.add(A[i]);
if(A[i] < Min)
Min = A[i];
}
}
if(Min>1 )
return 1;
int i = 1;
// 最小值等于 1
while(i<= A.length){
if(!list.contains(Min + i)){
MinInt = Min + i;
break;
}
i = i + 1;
}
return MinInt;
}
}
Java Code
总耗时: 2210 ms
这个和寻找缺失的数好像很像，虽然改写后的程序，理解不透，但是LeetCode的测试样例，造成无法通过
样例：[1,1]这样会陷入死循环。
程序如下
public class Solution {
/**
* @param A: an array of integers
* @return: an integer
*/
public int firstMissingPositive(int[] A) {
// write your code here
if(A.length == 0)
return 1;
int n = A.length;
for(int i =0 ;i< n ;i++){
while(A[i] != i + 1){
if(A[i] <= 0 || A[i] > n)
break;
int tmp = A[i];
A[i] = A[tmp - 1];
A[tmp - 1] = tmp;
}
}
for(int i =0;i< n ;i++)
if( A[i] != i+ 1)
return i+1;
return n + 1;
}
}
Java Code
class Solution:
# @param A, a list of integers
# @return an integer
def firstMissingPositive(self, A):
# write your code here
if A == None:
return 1
n = len(A)
nums = A[:]
for i in range(n):
while A[i] != i+1:
nums = A[:]
if A[i]<=0 or A[i]>=n:
break
tmp = A[i]
A[i] = A[tmp-1]
A[tmp-1] = tmp
# print 'before:',nums
# print 'later:',A
for i in range(n):
if A[i]!= i +1:
return i+1
return n +1
Python Code
====更新
在LeetCode讨论中看到的程序
public class Solution {
/**
* @param A: an array of integers
* @return: an integer
*/
public int firstMissingPositive(int[] A) {
// write your code here
//int[] A={2,1};
if(A.length == 0)
return 1;
int n = A.length;
for(int i = 0; i < n; ++ i){
int digit = A[i];
while(digit > 0 && digit <= n && A[digit - 1] != digit){
int tmp = A[i];
A[i] = A[digit -1];
A[digit -1] =tmp;
digit = A[i];
}
}
for(int i = 0; i < n; ++ i)
if(A[i] != i + 1)
return i + 1;
return n + 1;
}
}
这里的思想还是寻找缺失的数的思想
寻找缺失的数，原始序列是0 -N的，找出其中缺失的说，所以0是序列中的数，或者说0可能是答案
而这个题目是寻找第一个缺失的正整数，这里0不是答案，所以还要增加判断：A[A[i] - 1] !=A[i]
换个角度说就是让数组排序后是 1 2 3 4 的样式，第0个位置 应该是1 ，第1个位置应该是 2，第i个位置应该是i+1
对[3,4,-1,1]
第0个位置A[2]!=A[0] 交换后 :[-1,4,3,1]
第0个位置A[0]<0 跳出
第1个位置A[3]!=A[1]交换后:[-1,1,3,4]
第1个位置A[0]!=A[1]交换后:[1,-1,3,4]
第1个位置A[1]<0跳出
第2个位置A[2]==A[2]跳出
第3个位置A[3]==A[3]跳出
下面判断A[i] 是否等于i+1,第一个不满足条件的就是答案，i+1是答案，当都满足的时候就是n+1
Python
class Solution:
# @param A, a list of integers
# @return an integer
def firstMissingPositive(self, A):
# write your code here
if A == None:
return 1
n = len(A)
nums = A[:]
for i in range(n):
digit = A[i]
while digit>0 and digit<=n and A[digit -1] != digit:
A[i],A[digit -1] = A[digit-1],A[i]
digit = A[i]
for i in range(n):
if A[i]!= i +1:
return i+1
return n +1
说明：在交换的时候不用digit代替A[i] 交换无效。
最新文章
- [To do]Appx Package installed, can't start at first time
- WebApiTestClient自定义返回值说明
- 使用JavaScript获得星期几和每月多少天
- Core Java - 流(Stream) - 字节流和字符流(一)
- VS2015使用OSChina的git功能
- 2015第24周一Spring事务
- java生成json字符串的方法
- 使用nginx的rewrite实现代理指定文件夹命令方法
- HTML5学习笔记简明版（11）：新API
- 【C语言】指针模块
- mysql数据库和JDBC学习
- BigDecimal实现末尾去掉无用0
- PCI 设备调试手段
- log4j2配置推荐
- tortoiseSVN 合并代码方法
- week3b：个人博客作业
- 有关并查集的emmmm
- USACO 6.1 Postal Vans（一道神奇的dp）
- ubuntu上minigui调试环境的建立
- Scratch www 系统搭建