title 数字 span text 无效 run 复杂 etc
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 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
- }
第一个缺失数字
来源: http://www.bubuko.com/infodetail-2129089.html