首页 > 代码库 > leetcode .First Missing Positive
leetcode .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.
对于元素为n的数组A, 正数个数 <= n, 那么第一个miss的正数必然 <= n+1。这样，可以把负数置成n+2，不影响结果。
假设数字k 属于 [1, n]，且在数组A中的j位置出现，即A[j] = k。把数组A中所有的k置成-k, 那么留下第一个正数的位置j
即为第一个miss的正数。
1 int firstMissingPositive(int A[], int n) 2 { 3 int i = 0, temp = 0, inf = n + 2; 4 5 for (i = 0; i < n; i++) 6 A[i] = (A[i] <= 0) ? inf : A[i]; 7 8 for (i = 0; i < n; i++) 9 {10 temp = A[i] > 0 ? A[i] : -A[i];11 if (temp > n)12 continue;13 if (A[temp - 1] > 0) /* in case that A has duplicate value and A[temp - 1] will * -1 twice. */ 14 A[temp - 1] *= -1;15 }16 17 for (i = 0; i < n; i++)18 {19 if (A[i] > 0)20 return i + 1;21 }22 23 return i + 1;24 }
leetcode .First Missing Positive
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。