首页 > 代码库 > MissingInteger
MissingInteger
Task description
Write a function:
int solution(int A[], int N);
that, given a non-empty zero-indexed array A of N integers, returns the minimal positive integer that does not occur in A.
For example, given:
A[0] = 1 A[1] = 3 A[2] = 6 A[3] = 4 A[4] = 1 A[5] = 2
the function should return 5.
Assume that:
N is an integer within the range [1..100,000];
each element of array A is an integer within the range [2,147,483,648..2,147,483,647].
Complexity:
expected worst-case time complexity is O(N);
expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.
Solution C:20
int solution(int A[], int N) { int i = 0; int* temp = (int*)malloc(N*sizeof(int)); for( i = 0; i < N; i++ ) { temp[i] = 0x00; } for( i = 0; i < N; i++ ) { int position = A[i]-1; if(position >=0 && position < N ) { temp[position] = 1; } } for( i = 0; i < N; i++ ) { if(temp[i]==0) { break; } } free(temp); return i+1; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。