首页 > 代码库 > 第一个缺失数字
第一个缺失数字
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.
思路：
桶排的思想
从头到尾遍历数组，在位置 i，希望放置的元素是 i+1, 如果不是，
就把 A[ i ] 和 A[ A[i] -1 ] 的元素，这样就保证了 A[i]-1位置的元素是 A[i]，
不断重复上面这个过程，直到 A[ i ] == i+1 或者 A[i] 没有办法再交换，
A[i] 没有办法再交换的情况有：
A[i] <= 0: A[i]-1 是无效下标；
A[i] > n: A[i]-1 是无效下标；
A[i] == A[ A[i]-1]: 交换没有意义。
这样过后，有效的元素 i 一定放在了 A[i-1] 处，第一个 A[i] != i+1 的元素就是第一个缺少的正数了。
因为用的是桶排的思想，所以复杂度是 O(n).
public class Solution {
public int firstMissingPositive(int[] A) {
int n = A.length;
for(int i=0; i<n; i++){
//此处看上去是两层循环，但是在寻找A[i] == i+1 的过程中，
//不断将A[i]放在A[A[i]-1]处，循环到A[i]-1的时候就不用再处理,所以整体是O(n)
while(A[i] != i+1){
if(A[i]<=0 || A[i]>n || A[i]==A[A[i]-1])
break;
else{
//把A[i]放在A[i]-1处
int temp = A[i];
A[i] = A[temp-1];
A[temp-1] = temp;
}
}
}
for(int i=0; i<n; i++){
if(A[i] != i+1)
return i+1;
}
return n+1;
}
}
FirstMissingPositive问题描述：给一个没有排序的数组，找到第一个缺失的正数，例如nums={1，2，0}return3，nums={3，4，-1，1}return2
算法分析：既然是找正数，那么肯定是从1开始的，那么我们把1放在nums[0],以此类推，我们把数组中每个元素都放在它应该在的位置。那么找到下标和数字不相符的元素，下标+1即为缺失的正数。
public static int firstMissingPositive(int[] nums) {
int i = 0;
//将nums中每一个元素都放在它所代表的数字的位置上，例如nums[1]=4,那么nums[1]就应该放在第四个位置上，也就是nums[1]=nums[nums[1]-1]
//排除负数
while(i < nums.length)
{
if(nums[i] <= 0 || nums[i] > nums.length || nums[i] == i + 1 || nums[i] == nums[nums[i]-1])
{
i++;
}
else
{
int temp = nums[i];
nums[i] = nums[temp - 1];
nums[temp - 1] = temp;
}
}
int j = 0;
for(j = 0; j < nums.length; j ++)
{
if(nums[j] != j + 1)
{
return j+1;
}
}
return j+1;
}
《第一个缺失的正数》 http://www.cnblogs.com/masterlibin/p/5611822.html
《LeetCode112》 http://blog.csdn.net/javyzheng/article/details/40652409
《寻找第一个缺失数字》http://blog.csdn.net/lj_2_0_2/article/details/51336659
看完上述的3篇博文，总是有的地方考虑不清。直到看到一篇《【白话经典算法系列之十六】“基数排序”之数组中缺失的数字》 http://blog.csdn.net/morewindows/article/details/12683723 才豁然开朗。
以{1, 3, 6, -100, 2}为例来简介这种解法：
从第一个数字开始，由于a[0]=1，所以不用处理了。
第二个数字为3，因此放到第3个位置（下标为2），交换a[1]和a[2]，得到数组为{1, 6, 3, -100, 2}。由于6无法放入数组，所以直接跳过。
第三个数字是3，不用处理。
第四个数字是-100，也无法放入数组，直接跳过。
第五个数字是2，因此放到第2个位置（下标为1），交换a[4]和a[1]，得到数组为{1, 2, 3, -100, 6}，由于6无法放入数组，所以直接跳过。
此时“基数排序”就完成了，然后再从遍历数组，如果对于某个位置上没该数，就说明数组缺失了该数字。如{1, 2, 3, -100, 6}缺失的就为4。
这样，通过第i个位置上就放i的“基数排序”就顺利的搞定此题了。
1 // 【白话经典算法系列之十六】“基数排序”之数组中缺失的数字 2 // by MoreWindows( http://blog.csdn.net/MoreWindows ) 3 // 欢迎关注http://weibo.com/morewindows 4 #include <stdio.h> 5 void Swap(int &a, int &b) 6 { 7 int c = a; 8 a = b; 9 b = c; 10 } 11 int FindFirstNumberNotExistenceInArray(int a[], int n) 12 { 13 int i; 14 // 类似基数排序，当a[i]>0且a[i]<N时保证a[i] == i + 1 15 for (i = 0; i < n; i++) 16 while (a[i] > 0 && a[i] <= n && a[i] != i + 1 && a[i] != a[a[i] - 1]) 17 Swap(a[i], a[a[i] - 1]); 18 // 查看缺少哪个数 19 for (i = 0; i < n; i++) 20 if (a[i] != i + 1) 21 break; 22 return i + 1; 23 } 24 void PrintfArray(int a[], int n) 25 { 26 for (int i = 0; i < n; i++) 27 printf("%d ", a[i]); 28 putchar(‘\n‘); 29 } 30 int main() 31 { 32 printf(" 【白话经典算法系列之十六】“基数排序”之数组中缺失的数字\n"); 33 printf(" -- by MoreWindows( http://blog.csdn.net/MoreWindows ) --\n"); 34 printf(" -- http://blog.csdn.net/morewindows/article/details/12683723 -- \n\n"); 35 36 const int MAXN = 5; 37 //int a[MAXN] = {1, 2, 3, 4, 7}; 38 //int a[MAXN] = {1, 3, 5, 4, 2}; 39 int a[MAXN] = {2, -100, 4, 1, 70}; 40 //int a[MAXN] = {2, 2, 2, 2, 1}; 41 PrintfArray(a, MAXN); 42 printf("该数组缺失的数字为%d\n", FindFirstNumberNotExistenceInArray(a, MAXN)); 43 return 0; 44 }
第一个缺失数字