由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - find the first missing positive integer.
相关主题
这道题太神奇了,求排序算法,并且要求时间复杂度为O(n),空间复杂度O(1),再问一个C的malloc( )
给定一个数组,找出3个数乘积最大。Palantir面经
大家新年好。 请教一个 c interview question (转载)How to find the size of an array? Thanks.
关于数组size的问题菜鸟求问一个二维数组指针的问题 c++
一个N个数的int数组如何找到3个majority的数?C/C++里数组作函数的参数的话应该怎么写?
问一个bloomberg的面试题求指点一下我写的程序哪部分是C++ syntax
google youtube interview, 莫名被拒。。。。。。新鲜的苹果内核组悲剧出炉 今天晚上刚收到
面经-facebook, amazon,telenav, quantcast菜鸟问个问题,如果太简单了请原谅我的愚蠢
相关话题的讨论汇总
话题: int话题: return话题: min话题: max
进入JobHunting版参与讨论
1 (共1页)
d****o
发帖数: 1055
1
这道题谁能解出来?(注意,这道题题意请理解清楚)
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.
and [-3,-4,1,2,6,7] return 3
Your algorithm should run in O(n) time and uses constant space.
h****e
发帖数: 928
2
这道题在LeetCode上有的,叫做First Missing Positive
http://www.leetcode.com/onlinejudge
没做出来,但是网上可以找到解法的。
b***d
发帖数: 87
3
public static int findFirstMissPositive(int[] a)
{
Arrays.sort(a);
int i=0;
while(i {
if(a[i]<=0)
{
i++;
}
else
{
if(i+1 {
i++;
}
else
{
break;
}
}
}
return a[i]+1;
}
欢迎拍砖!
h****e
发帖数: 928
4
第一行做了排序,复杂度就变成O(nlogn)了。

【在 b***d 的大作中提到】
: public static int findFirstMissPositive(int[] a)
: {
: Arrays.sort(a);
: int i=0;
: while(i: {
: if(a[i]<=0)
: {
: i++;
: }

c****p
发帖数: 6474
5
换换换换换

【在 h****e 的大作中提到】
: 这道题在LeetCode上有的,叫做First Missing Positive
: http://www.leetcode.com/onlinejudge
: 没做出来,但是网上可以找到解法的。

s*******i
发帖数: 7
6
1.只考虑数组里的元素都>1的情况,因为其它任何数组可以在O(N)的复杂度内变成>1的
情况(用0做pivot把数组划开,<=0的部分不考虑)。
2.假设现在有数组A[1..N],且A[i]>1,那么有个“不”符合题目要求的线性算法:
设bool B[1..N],B[i]表示i在A[1..N]里出现过了,显然B数组线性时间就能算完。
但是它不符合题目中说的常数的额外空间。
3.我们想一下如何能把A和B只用A就表示了?
可以这样:因为A[i]>1,当我们在A[i]里看到一个元素j时,如果j>N就不用管,否则就
把A[j]里的数字变成负数。这样就可以用负号来代替那个B数组。
整个时间复杂度还是线性的,并且额外的空间是常数的。
l*********8
发帖数: 4642
7
int firstMissingPositive(int A[], int n) {
for (int i=0; i while (A[i] > 0 && A[i] <= n && A[i] != A[A[i]-1])
swap(A[i], A[A[i]-1]);
for (int i=0; i if(A[i] != i+1)
return i+1;
return n+1;
}
p*****2
发帖数: 21240
8
mark一下。
q***y
发帖数: 236
9
桶排
o*******y
发帖数: 115
10
写了个O(n)的
int firstPositive(int[] A)
{
int i = 0;
while(i < A.length)
{
if(A[i] < A.length && A[i] > 0 && A[A[i]] != A[i])
//把正数A[i]放到第i个位置
swap(A[i], A[A[i]]);
else
i++;
}
for(i = 1; i < A.length; i++)
{
if(A[i] != i) // 第i个位置上不是正数i则返回i
return i;
}
if(A[0] == A.length) // A[0]恰好是A.length则返回下一个正整数A.length+1
return A.length+1;
else // A[0] <=0 或者 > A.length, 则返回A.length
return A.length;
}
相关主题
问一个bloomberg的面试题再问一个C的malloc( )
google youtube interview, 莫名被拒。。。。。。Palantir面经
面经-facebook, amazon,telenav, quantcastHow to find the size of an array? Thanks.
进入JobHunting版参与讨论
r****k
发帖数: 21
11
重新构造数组,如果当前下标的value>0 && <=数组长度,则设置a[value-1] = value
例如原数组为: -3, -4, 1, 2, 6, 7
新数组为: 1, 2, 1, 2, 6, 6
然后循环数组,找到值不等于下标+1的i(a[i]!=i+1),返回i+1
int findFirstMissingPositive(int a[], int length)
{
int temp = 0;
int i = 0;
int value;
while (i < length)
{
if (temp > 0)
{
value = temp;
}
else
{
value = a[i];
i++;
}
if (value > 0 && value <= length)
{
if (a[value-1] == value)
{
temp = 0;
}
else
{
temp = a[value-1];
a[value-1] = value;
}
}
else
{
temp = 0;
}
}
for (i = 0; i < length; i++)
{
if (a[i] != i+1)
break;
}
return i+1;
}
l****c
发帖数: 782
12
我也mark一下吧,
不知道不用sort怎么找first missing positive,
用了sort就不O n 了
p*****2
发帖数: 21240
13

我发现我很懒的看代码。能说说思路吗?

【在 l*********8 的大作中提到】
: int firstMissingPositive(int A[], int n) {
: for (int i=0; i: while (A[i] > 0 && A[i] <= n && A[i] != A[A[i]-1])
: swap(A[i], A[A[i]-1]);
: for (int i=0; i: if(A[i] != i+1)
: return i+1;
: return n+1;
: }

p*****2
发帖数: 21240
14

chenpp的思路应该是对的。

【在 l****c 的大作中提到】
: 我也mark一下吧,
: 不知道不用sort怎么找first missing positive,
: 用了sort就不O n 了

w****x
发帖数: 2483
15

二爷, 你Facebook面的到底怎么样了??

【在 p*****2 的大作中提到】
:
: chenpp的思路应该是对的。

l*********8
发帖数: 4642
16
我的思路基本和onlysunny一样。

【在 p*****2 的大作中提到】
:
: chenpp的思路应该是对的。

h*****f
发帖数: 248
17
不知道我是不是解错题,如果输入的是[11,9,7,5],那第一个missing positive
integer= 4?
or the absolute value of the number must be between 0 and last index+1?
h*******s
发帖数: 8454
18
1

【在 h*****f 的大作中提到】
: 不知道我是不是解错题,如果输入的是[11,9,7,5],那第一个missing positive
: integer= 4?
: or the absolute value of the number must be between 0 and last index+1?

p*****2
发帖数: 21240
19
我写了一个
public int firstMissingPositive(int[] A)
{
int n = A.length;
int i = 0;
int j = n - 1;
while (i <= j)
{
while (i < n && A[i] >= 1 && A[i] <= n)
i++;
while (j >= 0 && (A[j] <= 0 || A[j] > n))
j--;
if (i < j)
{
int tmp = A[i];
A[i] = A[j];
A[j] = tmp;
i++;
j--;
}
}
for (i = 0; i <= j; i++)
{
int a = Math.abs(A[i]);
if (A[a - 1] > 0)
A[a - 1] = -A[a - 1];
}
for (i = 0; i <= j; i++)
if (A[i] > 0)
break;
return i + 1;
}
p*****2
发帖数: 21240
20

不行备,看你的了。

【在 w****x 的大作中提到】
:
: 二爷, 你Facebook面的到底怎么样了??

相关主题
菜鸟求问一个二维数组指针的问题 c++新鲜的苹果内核组悲剧出炉 今天晚上刚收到
C/C++里数组作函数的参数的话应该怎么写?菜鸟问个问题,如果太简单了请原谅我的愚蠢
求指点一下我写的程序哪部分是C++ syntaxhow to judge a linked list is palindrome?
进入JobHunting版参与讨论
j*******h
发帖数: 20
21
public class FirstMissingPositive {
int min;//Integer.MAX_VALUE;
int max;//Integer.MIN_VALUE;

private void checkMinMax(){
if( max > 0 && min > 0 ){
if( max < min ){
int temp = min;
min = max;
max = temp;
}
if( max - min > 1 )
max = -1;
}
}

public int firstMissingPositive(int[] A) {
// Start typing your Java solution below
// DO NOT write main() function
min = -1;
max = -1;
boolean hasOne = false;

if (A.length <= 0 )
return 1;
if(A.length == 1 && A[0] != 1)
return 1;
if(A.length == 1 && A[0] == 1)
return 2;

for (int i = 0; i < A.length; i++) {
if (A[i] <= 0)
continue;
if( A[i] == 1 )
hasOne = true;

// initialize
if( min == -1 ){
min = A[i];
checkMinMax();
continue;
}
if( max == -1 ){
max = A[i];
checkMinMax();
continue;
}

if (A[i] < min) {
max = min;
min = A[i];
checkMinMax();
}else if( A[i] > max ){
min = max;
max = A[i];
checkMinMax();
}
}
if( !hasOne )
return 1;
return max == -1 ? (min + 1) : (max + 1);
}
public static void main(String[] Args) {
int[] a = { -10,-3,-100,-1000,-239,1 };
int[] b = { 3,2 };
int[] c = { 2,2 };
int[] d = { 4, 1, 2, 3 };
FirstMissingPositive temp = new FirstMissingPositive();
System.out.println(Arrays.toString(a) + " --- "
+ temp.firstMissingPositive(a));
System.out.println(Arrays.toString(b) + " --- "
+ temp.firstMissingPositive(b));
System.out.println(Arrays.toString(c) + " --- "
+ temp.firstMissingPositive(c));
System.out.println(Arrays.toString(d) + " --- "
+ temp.firstMissingPositive(d));
}
}
H*******g
发帖数: 6997
22
呵呵,我习惯性的用QUERY来解决,供你参考

【在 d****o 的大作中提到】
: 这道题谁能解出来?(注意,这道题题意请理解清楚)
: 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.
: and [-3,-4,1,2,6,7] return 3
: Your algorithm should run in O(n) time and uses constant space.

y***d
发帖数: 2330
23
find the max, min, sum and the ought-to-be sum if there were nothing missing
pretty dummy solution though

【在 d****o 的大作中提到】
: 这道题谁能解出来?(注意,这道题题意请理解清楚)
: 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.
: and [-3,-4,1,2,6,7] return 3
: Your algorithm should run in O(n) time and uses constant space.

c*******a
发帖数: 35
24
如果这个数组只miss一个元素,那这是最有效的解法了。
但如果miss多个元素,就不行了。

missing

【在 y***d 的大作中提到】
: find the max, min, sum and the ought-to-be sum if there were nothing missing
: pretty dummy solution though

z********i
发帖数: 568
25
/* find the first missing postivie integer in array A with n elements
return x if one postive integer in [1..n] is missing;
return 0 otherwise;
*/
int findFirstMissingPositiveInteger(int A[], int n){
int x,i,val,index;
/* rearrange the input array A such that
B[i]=i+1 if i+1 exist in array A, or
B[i]=A[i] if i+1 does not exist in array A
where B is the array rearraged from A.
*/
for(i=0;i /* put A[i] in A[A[i]-1] if 1<=A[i]<=n && A[i]!=i+1 */
val=A[i];
while(val>0 && val<=n && val!=A[val-1]){
index=val-1;
val=A[index];
A[index]=index+1;
}
}
/* find the first missing postive integer A[i] where A[i]!=i+1 */
x=0; //return 0 if no missing postive integer from 1 to n
outFile<<"Array after rearraged"< for(i=0;i outFile< if(A[i]!=i+1){
x=i+1;
break;
}
}
outFile< return x;
}
Complexity is O(n) in time and O(1) in space.
The main difficulty on complexity is the while loop inside the for loop for
reordering. However, since each element in the range 1..n is only reordered
only once and each other element is not reordered, so the total complexity
is still O(n).
z********i
发帖数: 568
26
发现跟longway解法一样。longway解法更紧凑。

【在 z********i 的大作中提到】
: /* find the first missing postivie integer in array A with n elements
: return x if one postive integer in [1..n] is missing;
: return 0 otherwise;
: */
: int findFirstMissingPositiveInteger(int A[], int n){
: int x,i,val,index;
: /* rearrange the input array A such that
: B[i]=i+1 if i+1 exist in array A, or
: B[i]=A[i] if i+1 does not exist in array A
: where B is the array rearraged from A.

m*****k
发帖数: 731
27
try
new int[] {40,50,40, 10,20,30}

【在 p*****2 的大作中提到】
: 我写了一个
: public int firstMissingPositive(int[] A)
: {
: int n = A.length;
: int i = 0;
: int j = n - 1;
: while (i <= j)
: {
: while (i < n && A[i] >= 1 && A[i] <= n)
: i++;

m*****k
发帖数: 731
28
so won't work for [10,20,30] ?

【在 l*********8 的大作中提到】
: int firstMissingPositive(int A[], int n) {
: for (int i=0; i: while (A[i] > 0 && A[i] <= n && A[i] != A[A[i]-1])
: swap(A[i], A[A[i]-1]);
: for (int i=0; i: if(A[i] != i+1)
: return i+1;
: return n+1;
: }

l*********8
发帖数: 4642
29
it should return 1.

【在 m*****k 的大作中提到】
: so won't work for [10,20,30] ?
d*****i
发帖数: 122
30


【在 l*********8 的大作中提到】
: it should return 1.
相关主题
讨论一道算法给定一个数组,找出3个数乘积最大。
一题貌似在AMAZON和MICROSOFT都出现过的题目。大家新年好。 请教一个 c interview question (转载)
这道题太神奇了,求排序算法,并且要求时间复杂度为O(n),空间复杂度O(1),关于数组size的问题
进入JobHunting版参与讨论
l*********8
发帖数: 4642
31
我经常见到空回复。 不知道是什么意思?

【在 d*****i 的大作中提到】
:
C*******n
发帖数: 48
32
very easy
s*********5
发帖数: 514
33
int FindFirstMissingPositiveInteger(int a[], int size)
{
int index = 0;
while (index < size)
{
while (a[index] != index && a[index] < size
&& a[index] >0)
{
int tmp = a[a[index]];
a[a[index]] = a[index];
a[index] = tmp;
}
++index;
}
index = 1;
while (index < size)
{
if (a[index] != index)
return index;
++index;
}
return index;
};
int main(int argc, char* argv[])
{
int fff1[] = {1,2,0};
int fff2[] = {3, 4, -1, 1};
int fff3[] = {-3, -4, 1, 2, 6, 7};
int fff4[] = { -10,-3,-100,-1000,-239,1};
int fff5[] = {40,50,40, 10,20,30};
cout << " fff1: " << FindFirstMissingPositiveInteger(fff1, sizeof(fff1)/
sizeof(int)) << endl;
cout << " fff2: " << FindFirstMissingPositiveInteger(fff2, sizeof(fff2)/
sizeof(int)) << endl;
cout << " fff3: " << FindFirstMissingPositiveInteger(fff3, sizeof(fff3)/
sizeof(int)) << endl;
cout << " fff4: " << FindFirstMissingPositiveInteger(fff4, sizeof(fff4)/
sizeof(int)) << endl;
cout << " fff5: " << FindFirstMissingPositiveInteger(fff5, sizeof(fff5)/
sizeof(int)) << endl;
return 0;
}
Result:
fff1: 3
fff2: 2
fff3: 3
fff4: 2
fff5: 1
b**a
发帖数: 1118
34
Can we assume that there is no duplicated elements?
that is, there is no [-3,-4,1,2,6,6,7,7]

【在 d****o 的大作中提到】
: 这道题谁能解出来?(注意,这道题题意请理解清楚)
: 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.
: and [-3,-4,1,2,6,7] return 3
: Your algorithm should run in O(n) time and uses constant space.

g***m
发帖数: 85
35
数组full的空间可以无穷大...

【在 H*******g 的大作中提到】
: 呵呵,我习惯性的用QUERY来解决,供你参考
g***m
发帖数: 85
36
思路是对的,但是第一个loop扫一遍好像不够。
比如 3 4 -1 1
第一遍扫完是
-1 1 3 4
还要再来一遍,才能变成
1 -1 3 4
两遍也不够,这个扫的次数如果和n相关,就不是线性的了。

【在 l*********8 的大作中提到】
: int firstMissingPositive(int A[], int n) {
: for (int i=0; i: while (A[i] > 0 && A[i] <= n && A[i] != A[A[i]-1])
: swap(A[i], A[A[i]-1]);
: for (int i=0; i: if(A[i] != i+1)
: return i+1;
: return n+1;
: }

g**x
发帖数: 373
37
public int firstMissingPositive(int[] A) {
if (A.length == 0) return 1;

int i=0;
while (i if (A[i]>=0 && A[i] if (A[i]!=i && A[i]!=A[A[i]]) {
int temp = A[A[i]];
A[A[i]] = A[i];
A[i] = temp;
continue;
}
}
i++;
}

for (i=1; i if (i!=A[i]) return i;
}

if (A[0]==A.length) return A.length+1;

return A.length;
}

【在 g***m 的大作中提到】
: 思路是对的,但是第一个loop扫一遍好像不够。
: 比如 3 4 -1 1
: 第一遍扫完是
: -1 1 3 4
: 还要再来一遍,才能变成
: 1 -1 3 4
: 两遍也不够,这个扫的次数如果和n相关,就不是线性的了。

t**i
发帖数: 314
38
long的答案没有问题,每次swap后,i会保持原值在while loop里再检测一遍

【在 g***m 的大作中提到】
: 思路是对的,但是第一个loop扫一遍好像不够。
: 比如 3 4 -1 1
: 第一遍扫完是
: -1 1 3 4
: 还要再来一遍,才能变成
: 1 -1 3 4
: 两遍也不够,这个扫的次数如果和n相关,就不是线性的了。

g***s
发帖数: 3811
39
去年这个时候讨论过一次。
b********h
发帖数: 2451
40
使用一个原数组一样长的数组,
找出最小正整数...
int find_least_missing(const int numbers[],const int array_length)
{
int buffer_right[array_length];
for(int i=1;i {buffer_right[i]=0;}
int min_value=-1;
for (int i=1;i {
if (min_value>0) {
if (min_value>numbers[i])
min_value=numbers[i];
}
else{
if (numbers[i]>0)
min_value=numbers[i];
}
}
if (min_value>1)
return 1;
buffer_right[0]=min_value;
int total_number=array_length;
int max_right=0;
bool flag_right=0;
for (int i=1;i {
int distances;
distances=numbers[i]-min_value;
if (distances {
if (distances>0)
{buffer_right[distances]=numbers[i];
max_right=distances;}
else
total_number--;
}
else
{total_number--;
flag_right=1;
}
}
for (int i=1;i<=max_right;i++)
{
if(buffer_right[i]==0)
return min_value+i;
}
if (flag_right)
return max_right+min_value+1;
else
return 0;
}
相关主题
关于数组size的问题google youtube interview, 莫名被拒。。。。。。
一个N个数的int数组如何找到3个majority的数?面经-facebook, amazon,telenav, quantcast
问一个bloomberg的面试题再问一个C的malloc( )
进入JobHunting版参与讨论
d****o
发帖数: 1055
41
这道题谁能解出来?(注意,这道题题意请理解清楚)
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.
and [-3,-4,1,2,6,7] return 3
Your algorithm should run in O(n) time and uses constant space.
h****e
发帖数: 928
42
这道题在LeetCode上有的,叫做First Missing Positive
http://www.leetcode.com/onlinejudge
没做出来,但是网上可以找到解法的。
b***d
发帖数: 87
43
public static int findFirstMissPositive(int[] a)
{
Arrays.sort(a);
int i=0;
while(i {
if(a[i]<=0)
{
i++;
}
else
{
if(i+1 {
i++;
}
else
{
break;
}
}
}
return a[i]+1;
}
欢迎拍砖!
h****e
发帖数: 928
44
第一行做了排序,复杂度就变成O(nlogn)了。

【在 b***d 的大作中提到】
: public static int findFirstMissPositive(int[] a)
: {
: Arrays.sort(a);
: int i=0;
: while(i: {
: if(a[i]<=0)
: {
: i++;
: }

c****p
发帖数: 6474
45
换换换换换

【在 h****e 的大作中提到】
: 这道题在LeetCode上有的,叫做First Missing Positive
: http://www.leetcode.com/onlinejudge
: 没做出来,但是网上可以找到解法的。

s*******i
发帖数: 7
46
1.只考虑数组里的元素都>1的情况,因为其它任何数组可以在O(N)的复杂度内变成>1的
情况(用0做pivot把数组划开,<=0的部分不考虑)。
2.假设现在有数组A[1..N],且A[i]>1,那么有个“不”符合题目要求的线性算法:
设bool B[1..N],B[i]表示i在A[1..N]里出现过了,显然B数组线性时间就能算完。
但是它不符合题目中说的常数的额外空间。
3.我们想一下如何能把A和B只用A就表示了?
可以这样:因为A[i]>1,当我们在A[i]里看到一个元素j时,如果j>N就不用管,否则就
把A[j]里的数字变成负数。这样就可以用负号来代替那个B数组。
整个时间复杂度还是线性的,并且额外的空间是常数的。
l*********8
发帖数: 4642
47
int firstMissingPositive(int A[], int n) {
for (int i=0; i while (A[i] > 0 && A[i] <= n && A[i] != A[A[i]-1])
swap(A[i], A[A[i]-1]);
for (int i=0; i if(A[i] != i+1)
return i+1;
return n+1;
}
p*****2
发帖数: 21240
48
mark一下。
q***y
发帖数: 236
49
桶排
r****k
发帖数: 21
50
重新构造数组,如果当前下标的value>0 && <=数组长度,则设置a[value-1] = value
例如原数组为: -3, -4, 1, 2, 6, 7
新数组为: 1, 2, 1, 2, 6, 6
然后循环数组,找到值不等于下标+1的i(a[i]!=i+1),返回i+1
int findFirstMissingPositive(int a[], int length)
{
int temp = 0;
int i = 0;
int value;
while (i < length)
{
if (temp > 0)
{
value = temp;
}
else
{
value = a[i];
i++;
}
if (value > 0 && value <= length)
{
if (a[value-1] == value)
{
temp = 0;
}
else
{
temp = a[value-1];
a[value-1] = value;
}
}
else
{
temp = 0;
}
}
for (i = 0; i < length; i++)
{
if (a[i] != i+1)
break;
}
return i+1;
}
相关主题
Palantir面经C/C++里数组作函数的参数的话应该怎么写?
How to find the size of an array? Thanks.求指点一下我写的程序哪部分是C++ syntax
菜鸟求问一个二维数组指针的问题 c++新鲜的苹果内核组悲剧出炉 今天晚上刚收到
进入JobHunting版参与讨论
l****c
发帖数: 782
51
我也mark一下吧,
不知道不用sort怎么找first missing positive,
用了sort就不O n 了
p*****2
发帖数: 21240
52

我发现我很懒的看代码。能说说思路吗?

【在 l*********8 的大作中提到】
: int firstMissingPositive(int A[], int n) {
: for (int i=0; i: while (A[i] > 0 && A[i] <= n && A[i] != A[A[i]-1])
: swap(A[i], A[A[i]-1]);
: for (int i=0; i: if(A[i] != i+1)
: return i+1;
: return n+1;
: }

p*****2
发帖数: 21240
53

chenpp的思路应该是对的。

【在 l****c 的大作中提到】
: 我也mark一下吧,
: 不知道不用sort怎么找first missing positive,
: 用了sort就不O n 了

w****x
发帖数: 2483
54

二爷, 你Facebook面的到底怎么样了??

【在 p*****2 的大作中提到】
:
: chenpp的思路应该是对的。

l*********8
发帖数: 4642
55
我的思路基本和onlysunny一样。

【在 p*****2 的大作中提到】
:
: chenpp的思路应该是对的。

h*****f
发帖数: 248
56
不知道我是不是解错题,如果输入的是[11,9,7,5],那第一个missing positive
integer= 4?
or the absolute value of the number must be between 0 and last index+1?
h*******s
发帖数: 8454
57
1

【在 h*****f 的大作中提到】
: 不知道我是不是解错题,如果输入的是[11,9,7,5],那第一个missing positive
: integer= 4?
: or the absolute value of the number must be between 0 and last index+1?

p*****2
发帖数: 21240
58
我写了一个
public int firstMissingPositive(int[] A)
{
int n = A.length;
int i = 0;
int j = n - 1;
while (i <= j)
{
while (i < n && A[i] >= 1 && A[i] <= n)
i++;
while (j >= 0 && (A[j] <= 0 || A[j] > n))
j--;
if (i < j)
{
int tmp = A[i];
A[i] = A[j];
A[j] = tmp;
i++;
j--;
}
}
for (i = 0; i <= j; i++)
{
int a = Math.abs(A[i]);
if (A[a - 1] > 0)
A[a - 1] = -A[a - 1];
}
for (i = 0; i <= j; i++)
if (A[i] > 0)
break;
return i + 1;
}
p*****2
发帖数: 21240
59

不行备,看你的了。

【在 w****x 的大作中提到】
:
: 二爷, 你Facebook面的到底怎么样了??

j*******h
发帖数: 20
60
public class FirstMissingPositive {
int min;//Integer.MAX_VALUE;
int max;//Integer.MIN_VALUE;

private void checkMinMax(){
if( max > 0 && min > 0 ){
if( max < min ){
int temp = min;
min = max;
max = temp;
}
if( max - min > 1 )
max = -1;
}
}

public int firstMissingPositive(int[] A) {
// Start typing your Java solution below
// DO NOT write main() function
min = -1;
max = -1;
boolean hasOne = false;

if (A.length <= 0 )
return 1;
if(A.length == 1 && A[0] != 1)
return 1;
if(A.length == 1 && A[0] == 1)
return 2;

for (int i = 0; i < A.length; i++) {
if (A[i] <= 0)
continue;
if( A[i] == 1 )
hasOne = true;

// initialize
if( min == -1 ){
min = A[i];
checkMinMax();
continue;
}
if( max == -1 ){
max = A[i];
checkMinMax();
continue;
}

if (A[i] < min) {
max = min;
min = A[i];
checkMinMax();
}else if( A[i] > max ){
min = max;
max = A[i];
checkMinMax();
}
}
if( !hasOne )
return 1;
return max == -1 ? (min + 1) : (max + 1);
}
public static void main(String[] Args) {
int[] a = { -10,-3,-100,-1000,-239,1 };
int[] b = { 3,2 };
int[] c = { 2,2 };
int[] d = { 4, 1, 2, 3 };
FirstMissingPositive temp = new FirstMissingPositive();
System.out.println(Arrays.toString(a) + " --- "
+ temp.firstMissingPositive(a));
System.out.println(Arrays.toString(b) + " --- "
+ temp.firstMissingPositive(b));
System.out.println(Arrays.toString(c) + " --- "
+ temp.firstMissingPositive(c));
System.out.println(Arrays.toString(d) + " --- "
+ temp.firstMissingPositive(d));
}
}
相关主题
菜鸟问个问题,如果太简单了请原谅我的愚蠢一题貌似在AMAZON和MICROSOFT都出现过的题目。
how to judge a linked list is palindrome?这道题太神奇了,求排序算法,并且要求时间复杂度为O(n),空间复杂度O(1),
讨论一道算法给定一个数组,找出3个数乘积最大。
进入JobHunting版参与讨论
H*******g
发帖数: 6997
61
呵呵,我习惯性的用QUERY来解决,供你参考

【在 d****o 的大作中提到】
: 这道题谁能解出来?(注意,这道题题意请理解清楚)
: 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.
: and [-3,-4,1,2,6,7] return 3
: Your algorithm should run in O(n) time and uses constant space.

y***d
发帖数: 2330
62
find the max, min, sum and the ought-to-be sum if there were nothing missing
pretty dummy solution though

【在 d****o 的大作中提到】
: 这道题谁能解出来?(注意,这道题题意请理解清楚)
: 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.
: and [-3,-4,1,2,6,7] return 3
: Your algorithm should run in O(n) time and uses constant space.

c*******a
发帖数: 35
63
如果这个数组只miss一个元素,那这是最有效的解法了。
但如果miss多个元素,就不行了。

missing

【在 y***d 的大作中提到】
: find the max, min, sum and the ought-to-be sum if there were nothing missing
: pretty dummy solution though

z********i
发帖数: 568
64
/* find the first missing postivie integer in array A with n elements
return x if one postive integer in [1..n] is missing;
return 0 otherwise;
*/
int findFirstMissingPositiveInteger(int A[], int n){
int x,i,val,index;
/* rearrange the input array A such that
B[i]=i+1 if i+1 exist in array A, or
B[i]=A[i] if i+1 does not exist in array A
where B is the array rearraged from A.
*/
for(i=0;i /* put A[i] in A[A[i]-1] if 1<=A[i]<=n && A[i]!=i+1 */
val=A[i];
while(val>0 && val<=n && val!=A[val-1]){
index=val-1;
val=A[index];
A[index]=index+1;
}
}
/* find the first missing postive integer A[i] where A[i]!=i+1 */
x=0; //return 0 if no missing postive integer from 1 to n
outFile<<"Array after rearraged"< for(i=0;i outFile< if(A[i]!=i+1){
x=i+1;
break;
}
}
outFile< return x;
}
Complexity is O(n) in time and O(1) in space.
The main difficulty on complexity is the while loop inside the for loop for
reordering. However, since each element in the range 1..n is only reordered
only once and each other element is not reordered, so the total complexity
is still O(n).
z********i
发帖数: 568
65
发现跟longway解法一样。longway解法更紧凑。

【在 z********i 的大作中提到】
: /* find the first missing postivie integer in array A with n elements
: return x if one postive integer in [1..n] is missing;
: return 0 otherwise;
: */
: int findFirstMissingPositiveInteger(int A[], int n){
: int x,i,val,index;
: /* rearrange the input array A such that
: B[i]=i+1 if i+1 exist in array A, or
: B[i]=A[i] if i+1 does not exist in array A
: where B is the array rearraged from A.

m*****k
发帖数: 731
66
try
new int[] {40,50,40, 10,20,30}

【在 p*****2 的大作中提到】
: 我写了一个
: public int firstMissingPositive(int[] A)
: {
: int n = A.length;
: int i = 0;
: int j = n - 1;
: while (i <= j)
: {
: while (i < n && A[i] >= 1 && A[i] <= n)
: i++;

m*****k
发帖数: 731
67
so won't work for [10,20,30] ?

【在 l*********8 的大作中提到】
: int firstMissingPositive(int A[], int n) {
: for (int i=0; i: while (A[i] > 0 && A[i] <= n && A[i] != A[A[i]-1])
: swap(A[i], A[A[i]-1]);
: for (int i=0; i: if(A[i] != i+1)
: return i+1;
: return n+1;
: }

l*********8
发帖数: 4642
68
it should return 1.

【在 m*****k 的大作中提到】
: so won't work for [10,20,30] ?
l*********8
发帖数: 4642
69
我经常见到空回复。 不知道是什么意思?

【在 d*****i 的大作中提到】
:
C*******n
发帖数: 48
70
very easy
相关主题
给定一个数组,找出3个数乘积最大。一个N个数的int数组如何找到3个majority的数?
大家新年好。 请教一个 c interview question (转载)问一个bloomberg的面试题
关于数组size的问题google youtube interview, 莫名被拒。。。。。。
进入JobHunting版参与讨论
s*********5
发帖数: 514
71
int FindFirstMissingPositiveInteger(int a[], int size)
{
int index = 0;
while (index < size)
{
while (a[index] != index && a[index] < size
&& a[index] >0)
{
int tmp = a[a[index]];
a[a[index]] = a[index];
a[index] = tmp;
}
++index;
}
index = 1;
while (index < size)
{
if (a[index] != index)
return index;
++index;
}
return index;
};
int main(int argc, char* argv[])
{
int fff1[] = {1,2,0};
int fff2[] = {3, 4, -1, 1};
int fff3[] = {-3, -4, 1, 2, 6, 7};
int fff4[] = { -10,-3,-100,-1000,-239,1};
int fff5[] = {40,50,40, 10,20,30};
cout << " fff1: " << FindFirstMissingPositiveInteger(fff1, sizeof(fff1)/
sizeof(int)) << endl;
cout << " fff2: " << FindFirstMissingPositiveInteger(fff2, sizeof(fff2)/
sizeof(int)) << endl;
cout << " fff3: " << FindFirstMissingPositiveInteger(fff3, sizeof(fff3)/
sizeof(int)) << endl;
cout << " fff4: " << FindFirstMissingPositiveInteger(fff4, sizeof(fff4)/
sizeof(int)) << endl;
cout << " fff5: " << FindFirstMissingPositiveInteger(fff5, sizeof(fff5)/
sizeof(int)) << endl;
return 0;
}
Result:
fff1: 3
fff2: 2
fff3: 3
fff4: 2
fff5: 1
b**a
发帖数: 1118
72
Can we assume that there is no duplicated elements?
that is, there is no [-3,-4,1,2,6,6,7,7]

【在 d****o 的大作中提到】
: 这道题谁能解出来?(注意,这道题题意请理解清楚)
: 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.
: and [-3,-4,1,2,6,7] return 3
: Your algorithm should run in O(n) time and uses constant space.

g***m
发帖数: 85
73
数组full的空间可以无穷大...

【在 H*******g 的大作中提到】
: 呵呵,我习惯性的用QUERY来解决,供你参考
g***m
发帖数: 85
74
思路是对的,但是第一个loop扫一遍好像不够。
比如 3 4 -1 1
第一遍扫完是
-1 1 3 4
还要再来一遍,才能变成
1 -1 3 4
两遍也不够,这个扫的次数如果和n相关,就不是线性的了。

【在 l*********8 的大作中提到】
: int firstMissingPositive(int A[], int n) {
: for (int i=0; i: while (A[i] > 0 && A[i] <= n && A[i] != A[A[i]-1])
: swap(A[i], A[A[i]-1]);
: for (int i=0; i: if(A[i] != i+1)
: return i+1;
: return n+1;
: }

g**x
发帖数: 373
75
public int firstMissingPositive(int[] A) {
if (A.length == 0) return 1;

int i=0;
while (i if (A[i]>=0 && A[i] if (A[i]!=i && A[i]!=A[A[i]]) {
int temp = A[A[i]];
A[A[i]] = A[i];
A[i] = temp;
continue;
}
}
i++;
}

for (i=1; i if (i!=A[i]) return i;
}

if (A[0]==A.length) return A.length+1;

return A.length;
}

【在 g***m 的大作中提到】
: 思路是对的,但是第一个loop扫一遍好像不够。
: 比如 3 4 -1 1
: 第一遍扫完是
: -1 1 3 4
: 还要再来一遍,才能变成
: 1 -1 3 4
: 两遍也不够,这个扫的次数如果和n相关,就不是线性的了。

t**i
发帖数: 314
76
long的答案没有问题,每次swap后,i会保持原值在while loop里再检测一遍

【在 g***m 的大作中提到】
: 思路是对的,但是第一个loop扫一遍好像不够。
: 比如 3 4 -1 1
: 第一遍扫完是
: -1 1 3 4
: 还要再来一遍,才能变成
: 1 -1 3 4
: 两遍也不够,这个扫的次数如果和n相关,就不是线性的了。

g***s
发帖数: 3811
77
去年这个时候讨论过一次。
b********h
发帖数: 2451
78
使用一个原数组一样长的数组,
找出最小正整数...
int find_least_missing(const int numbers[],const int array_length)
{
int buffer_right[array_length];
for(int i=1;i {buffer_right[i]=0;}
int min_value=-1;
for (int i=1;i {
if (min_value>0) {
if (min_value>numbers[i])
min_value=numbers[i];
}
else{
if (numbers[i]>0)
min_value=numbers[i];
}
}
if (min_value>1)
return 1;
buffer_right[0]=min_value;
int total_number=array_length;
int max_right=0;
bool flag_right=0;
for (int i=1;i {
int distances;
distances=numbers[i]-min_value;
if (distances {
if (distances>0)
{buffer_right[distances]=numbers[i];
max_right=distances;}
else
total_number--;
}
else
{total_number--;
flag_right=1;
}
}
for (int i=1;i<=max_right;i++)
{
if(buffer_right[i]==0)
return min_value+i;
}
if (flag_right)
return max_right+min_value+1;
else
return 0;
}
j**7
发帖数: 143
79
static int findPositive(int [] input)
{
int length=input.length;
for(int i=0;i {
if(input[i]!=i+1 && input[i]<=length &&input[i]>=1)
{
int temp=input[i];
input[i]=input[input[i]-1];
input[temp-1]=temp;
}
}
for(int i=0;i {
if(input[i]!=i+1)
return i+1;
}

return length+1;
}
A***o
发帖数: 358
80
O(n) time, O(n) space
int find(vector & input){
vector check;
check.resize(input.size(),0);
for(int i=0;i if(input[i]>0 && input[i]<=input.size())
check[ input[i]-1 ]=input[i];
}
for(int i=0;i if(check[i]==0)
return i+1;
}
return check.size()+1;
}
相关主题
面经-facebook, amazon,telenav, quantcastHow to find the size of an array? Thanks.
再问一个C的malloc( )菜鸟求问一个二维数组指针的问题 c++
Palantir面经C/C++里数组作函数的参数的话应该怎么写?
进入JobHunting版参与讨论
b*******e
发帖数: 217
81
build a min-heap in o(n).
query the min element.
query the two child ot he min element.
if the three elements not consecutive. find the missing interger already.
Otherwiese, go to the smaller child until the missing integer is found. o(
logn)
complexity = o(n) + o(logn)

【在 d****o 的大作中提到】
: 这道题谁能解出来?(注意,这道题题意请理解清楚)
: 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.
: and [-3,-4,1,2,6,7] return 3
: Your algorithm should run in O(n) time and uses constant space.

b*******e
发帖数: 217
82
the agorithm using -1 mentioned by others earleir is the best.
Is the algorithm below oky? seems to me no extra space is needed though....
evyerthing can be in-place?

【在 b*******e 的大作中提到】
: build a min-heap in o(n).
: query the min element.
: query the two child ot he min element.
: if the three elements not consecutive. find the missing interger already.
: Otherwiese, go to the smaller child until the missing integer is found. o(
: logn)
: complexity = o(n) + o(logn)

a******e
发帖数: 710
83
min-heap的building time不是o(n logn) 么?

【在 b*******e 的大作中提到】
: build a min-heap in o(n).
: query the min element.
: query the two child ot he min element.
: if the three elements not consecutive. find the missing interger already.
: Otherwiese, go to the smaller child until the missing integer is found. o(
: logn)
: complexity = o(n) + o(logn)

c******5
发帖数: 84
84
public int firstMissingPositive(int[] A) {
// Start typing your Java solution below
// DO NOT write main() function
if (A.length == 0) {// if A is empty, that means '1' is the missing
// positive
return 1;
}
for (int i = 0; i < A.length; i++) {
if (A[i] > 0 && (A[i] - 1 < A.length) && A[A[i] - 1] != A[i]) {
int temp = A[A[i] - 1];
A[A[i] - 1] = A[i];
A[i] = temp;
i--;//continue doing A[i]
}
}
int j = 1;
while (j <= A.length && A[j - 1] == j) {
j++;
}
return j;
}
m*********g
发帖数: 170
85
换换换换的思路:
假设数组S个数为n。我从1开始,S[1]如果是3,我就将它放到3的位置。即S[1]和s[3]
swap。再看s[1]的值,将其放到对应的位置。直到s[1]==1,我们看s[2]。以此类推。
我们停止的地方就是要求的值。
b*******e
发帖数: 217
86


【在 a******e 的大作中提到】
: min-heap的building time不是o(n logn) 么?
b*******e
发帖数: 217
87
build heap is O(n). see CLS
a***o
发帖数: 1182
88
如果s[1]一直不是1,停下来的条件是啥?

【在 m*********g 的大作中提到】
: 换换换换的思路:
: 假设数组S个数为n。我从1开始,S[1]如果是3,我就将它放到3的位置。即S[1]和s[3]
: swap。再看s[1]的值,将其放到对应的位置。直到s[1]==1,我们看s[2]。以此类推。
: 我们停止的地方就是要求的值。

m*********g
发帖数: 170
89
believeme是对的。用heap。
B********t
发帖数: 147
90
停下来的条件是 s[1] == s[s[1]]

【在 a***o 的大作中提到】
: 如果s[1]一直不是1,停下来的条件是啥?
相关主题
求指点一下我写的程序哪部分是C++ syntaxhow to judge a linked list is palindrome?
新鲜的苹果内核组悲剧出炉 今天晚上刚收到讨论一道算法
菜鸟问个问题,如果太简单了请原谅我的愚蠢一题貌似在AMAZON和MICROSOFT都出现过的题目。
进入JobHunting版参与讨论
m*****1
发帖数: 147
91
能解释一下你的思路吗??

missing

【在 c******5 的大作中提到】
: public int firstMissingPositive(int[] A) {
: // Start typing your Java solution below
: // DO NOT write main() function
: if (A.length == 0) {// if A is empty, that means '1' is the missing
: // positive
: return 1;
: }
: for (int i = 0; i < A.length; i++) {
: if (A[i] > 0 && (A[i] - 1 < A.length) && A[A[i] - 1] != A[i]) {
: int temp = A[A[i] - 1];

c******5
发帖数: 84
92
恩 我的思路是这样的:
不断的swap 碰到零或者负数就跳过,把正数A[i]swap到A[i]-1的位置,但要注意数组
的越界,所以有A[i] - 1 < A.length这个条件,由于swap后得到的新数可能也需要新的
swap,所以有i--
最后从位置0开始找第一个A[i-1]!=i的数,return i
比如0.4,1,2
0,4,1,2->1,4,0,2->1,2,0,4

【在 m*****1 的大作中提到】
: 能解释一下你的思路吗??
:
: missing

t*********r
发帖数: 845
93
新手,欢迎大家拍砖
假设数组有n个大于0的而且不重复的整数,
(1) sum all elements, if sum=n(n+1)/2, then we know its n+1
(2) if not, compare with n/2, we will have two new arrays, one contains
elements <= n/2, one >n/2. Subtract the second one with n/2. find the sum of
first array, if sum=n'(n'+1)/2, the missing element must be in the second
array
(3) split the second one into two by comparing with n/4, and repeat again..

【在 d****o 的大作中提到】
: 这道题谁能解出来?(注意,这道题题意请理解清楚)
: 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.
: and [-3,-4,1,2,6,7] return 3
: Your algorithm should run in O(n) time and uses constant space.

N*D
发帖数: 3641
94
俺也凑个热闹,贴个code
Run Status: Accepted!
Program Runtime: 564 milli secs
Progress: 156/156 test cases passed.
public class Solution {

public int firstMissingPositive(int[] A) {
// Start typing your Java solution below
// DO NOT write main() function
int length = A.length;
int i = 0;
while (i < length) {
// for pointer i, swap until the condition is broken.
while ((A[i] > 0) && (A[i] < length) && (A[i] != i+1)) {
if (A[A[i]-1] != A[i]) {
int tmp = A[A[i]-1];
A[A[i]-1] = A[i];
A[i] = tmp;
} else {
break;
}
}
i++;
}

for (i = 0; i < length; i++) {
if (A[i] != i+1) {
return i+1;
}
}
return length+1;
}
}
Leetcode的test case真全啊,第一次的while loop忘记加判断碰上{1,1}就死循环了。
。。
j**7
发帖数: 143
95
public int firstMissingPositive(int[] input) {
// Start typing your Java solution below
// DO NOT write main() function

int length=input.length;
for(int i=0;i {

while (input[i]!=i+1 && input[i]<=length &&input[i]>=1)
{
if(input[i]==input[input[i]-1])
break;
int temp=input[i];
input[i]=input[input[i]-1];
input[temp-1]=temp;
}
}


for(int i=0;i {
if(input[i]!=i+1)
return i+1;
}

return length+1;

}
A***o
发帖数: 358
96
O(n) time, O(n) space
int find(vector & input){
vector check;
check.resize(input.size(),0);
for(int i=0;i if(input[i]>0 && input[i]<=input.size())
check[ input[i]-1 ]=input[i];
}
for(int i=0;i if(check[i]==0)
return i+1;
}
return check.size()+1;
}
b*******e
发帖数: 217
97
build a min-heap in o(n).
query the min element.
query the two child ot he min element.
if the three elements not consecutive. find the missing interger already.
Otherwiese, go to the smaller child until the missing integer is found. o(
logn)
complexity = o(n) + o(logn)

【在 d****o 的大作中提到】
: 这道题谁能解出来?(注意,这道题题意请理解清楚)
: 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.
: and [-3,-4,1,2,6,7] return 3
: Your algorithm should run in O(n) time and uses constant space.

b*******e
发帖数: 217
98
the agorithm using -1 mentioned by others earleir is the best.
Is the algorithm below oky? seems to me no extra space is needed though....
evyerthing can be in-place?

【在 b*******e 的大作中提到】
: build a min-heap in o(n).
: query the min element.
: query the two child ot he min element.
: if the three elements not consecutive. find the missing interger already.
: Otherwiese, go to the smaller child until the missing integer is found. o(
: logn)
: complexity = o(n) + o(logn)

a******e
发帖数: 710
99
min-heap的building time不是o(n logn) 么?

【在 b*******e 的大作中提到】
: build a min-heap in o(n).
: query the min element.
: query the two child ot he min element.
: if the three elements not consecutive. find the missing interger already.
: Otherwiese, go to the smaller child until the missing integer is found. o(
: logn)
: complexity = o(n) + o(logn)

c******5
发帖数: 84
100
public int firstMissingPositive(int[] A) {
// Start typing your Java solution below
// DO NOT write main() function
if (A.length == 0) {// if A is empty, that means '1' is the missing
// positive
return 1;
}
for (int i = 0; i < A.length; i++) {
if (A[i] > 0 && (A[i] - 1 < A.length) && A[A[i] - 1] != A[i]) {
int temp = A[A[i] - 1];
A[A[i] - 1] = A[i];
A[i] = temp;
i--;//continue doing A[i]
}
}
int j = 1;
while (j <= A.length && A[j - 1] == j) {
j++;
}
return j;
}
相关主题
这道题太神奇了,求排序算法,并且要求时间复杂度为O(n),空间复杂度O(1),关于数组size的问题
给定一个数组,找出3个数乘积最大。一个N个数的int数组如何找到3个majority的数?
大家新年好。 请教一个 c interview question (转载)问一个bloomberg的面试题
进入JobHunting版参与讨论
m*********g
发帖数: 170
101
换换换换的思路:
假设数组S个数为n。我从1开始,S[1]如果是3,我就将它放到3的位置。即S[1]和s[3]
swap。再看s[1]的值,将其放到对应的位置。直到s[1]==1,我们看s[2]。以此类推。
我们停止的地方就是要求的值。
b*******e
发帖数: 217
102


【在 a******e 的大作中提到】
: min-heap的building time不是o(n logn) 么?
b*******e
发帖数: 217
103
build heap is O(n). see CLS
a***o
发帖数: 1182
104
如果s[1]一直不是1,停下来的条件是啥?

【在 m*********g 的大作中提到】
: 换换换换的思路:
: 假设数组S个数为n。我从1开始,S[1]如果是3,我就将它放到3的位置。即S[1]和s[3]
: swap。再看s[1]的值,将其放到对应的位置。直到s[1]==1,我们看s[2]。以此类推。
: 我们停止的地方就是要求的值。

m*********g
发帖数: 170
105
believeme是对的。用heap。
B********t
发帖数: 147
106
停下来的条件是 s[1] == s[s[1]]

【在 a***o 的大作中提到】
: 如果s[1]一直不是1,停下来的条件是啥?
m*****1
发帖数: 147
107
能解释一下你的思路吗??

missing

【在 c******5 的大作中提到】
: public int firstMissingPositive(int[] A) {
: // Start typing your Java solution below
: // DO NOT write main() function
: if (A.length == 0) {// if A is empty, that means '1' is the missing
: // positive
: return 1;
: }
: for (int i = 0; i < A.length; i++) {
: if (A[i] > 0 && (A[i] - 1 < A.length) && A[A[i] - 1] != A[i]) {
: int temp = A[A[i] - 1];

c******5
发帖数: 84
108
恩 我的思路是这样的:
不断的swap 碰到零或者负数就跳过,把正数A[i]swap到A[i]-1的位置,但要注意数组
的越界,所以有A[i] - 1 < A.length这个条件,由于swap后得到的新数可能也需要新的
swap,所以有i--
最后从位置0开始找第一个A[i-1]!=i的数,return i
比如0.4,1,2
0,4,1,2->1,4,0,2->1,2,0,4

【在 m*****1 的大作中提到】
: 能解释一下你的思路吗??
:
: missing

t*********r
发帖数: 845
109
新手,欢迎大家拍砖
假设数组有n个大于0的而且不重复的整数,
(1) sum all elements, if sum=n(n+1)/2, then we know its n+1
(2) if not, compare with n/2, we will have two new arrays, one contains
elements <= n/2, one >n/2. Subtract the second one with n/2. find the sum of
first array, if sum=n'(n'+1)/2, the missing element must be in the second
array
(3) split the second one into two by comparing with n/4, and repeat again..

【在 d****o 的大作中提到】
: 这道题谁能解出来?(注意,这道题题意请理解清楚)
: 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.
: and [-3,-4,1,2,6,7] return 3
: Your algorithm should run in O(n) time and uses constant space.

N*D
发帖数: 3641
110
俺也凑个热闹,贴个code
Run Status: Accepted!
Program Runtime: 564 milli secs
Progress: 156/156 test cases passed.
public class Solution {

public int firstMissingPositive(int[] A) {
// Start typing your Java solution below
// DO NOT write main() function
int length = A.length;
int i = 0;
while (i < length) {
// for pointer i, swap until the condition is broken.
while ((A[i] > 0) && (A[i] < length) && (A[i] != i+1)) {
if (A[A[i]-1] != A[i]) {
int tmp = A[A[i]-1];
A[A[i]-1] = A[i];
A[i] = tmp;
} else {
break;
}
}
i++;
}

for (i = 0; i < length; i++) {
if (A[i] != i+1) {
return i+1;
}
}
return length+1;
}
}
Leetcode的test case真全啊,第一次的while loop忘记加判断碰上{1,1}就死循环了。
。。
相关主题
问一个bloomberg的面试题再问一个C的malloc( )
google youtube interview, 莫名被拒。。。。。。Palantir面经
面经-facebook, amazon,telenav, quantcastHow to find the size of an array? Thanks.
进入JobHunting版参与讨论
w***o
发帖数: 109
111
我用两个指针两遍夹的方法:
public int firstMissingPositive(int[] A) {
int l = 0, r = A.length-1;
while(l <= r) {
int x = A[l];
if(x == l+1) {
l++;
continue;
}
if(x <= l || x > r+1 || A[x-1] == x) {
A[l] = A[r--];
} else {
A[l] = A[x-1];
A[x-1] = x;
}
}
return l+1;
}
o****d
发帖数: 2835
112
思路:
O(n)复杂度。一个长度为n的数组,缺失的第一个数一定是在[1,n+1]范围内。
把所有的数换到index对应的位置,比如把1放到A[1], 2放到A[2]...
这样做完之后 如果A[i]!=i的话 那就是i缺失了 (按上面换法,A[0]应该为n)
数字对调的判断条件中注意 1)如果i不在数组index范围内就skip 2)有duplicate的情
况下,A[i]=A[A[i]]也skip
class Solution {
public:
int firstMissingPositive(int A[], int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
for(int i=0; i {
while(A[i]>=0 && A[i] { int tmp=A[A[i]]; A[A[i]]=A[i]; A[i]=tmp;}
}
for(int i=1; i if(A[i]!=i) return i;
if(A[0]!=n) return n;
return n+1;
}
};

【在 B********t 的大作中提到】
: 停下来的条件是 s[1] == s[s[1]]
1 (共1页)
进入JobHunting版参与讨论
相关主题
菜鸟问个问题,如果太简单了请原谅我的愚蠢一个N个数的int数组如何找到3个majority的数?
how to judge a linked list is palindrome?问一个bloomberg的面试题
讨论一道算法google youtube interview, 莫名被拒。。。。。。
一题貌似在AMAZON和MICROSOFT都出现过的题目。面经-facebook, amazon,telenav, quantcast
这道题太神奇了,求排序算法,并且要求时间复杂度为O(n),空间复杂度O(1),再问一个C的malloc( )
给定一个数组,找出3个数乘积最大。Palantir面经
大家新年好。 请教一个 c interview question (转载)How to find the size of an array? Thanks.
关于数组size的问题菜鸟求问一个二维数组指针的问题 c++
相关话题的讨论汇总
话题: int话题: return话题: min话题: max