[코딜리티] codility lesson3 Time Complexity - PermMissingElem 100%
문제.
풀이.
설명.
Programming language:
A zero-indexed array A consisting of N different integers is given. The array contains integers in the range [1..(N + 1)], which means that exactly one element is missing.
Your goal is to find that missing element.
Write a function:
int solution(int A[], int N);
that, given a zero-indexed array A, returns the value of the missing element.
For example, given array A such that:
A[0] = 2
A[1] = 3
A[2] = 1
A[3] = 5
the function should return 4, as it is the missing element.
Assume that:
- N is an integer within the range [0..100,000];
- the elements of A are all distinct;
- each element of array A is an integer within the range [1..(N + 1)].
Complexity:
- expected worst-case time complexity is O(N);
- expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.
Copyright 2009–2017 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
풀이.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int[] A) {
// write your code in Java SE 8
int[] arrN = new int[A.length+2];
for( int i = 0 ; i < A.length ; i++) arrN[A[i]] = A[i];
for( int i = 1 ; i < arrN.length ; i++) if(arrN[i] == 0 ) return i;
return 0;
}
}
| cs |
설명.
카드뽑기. 단순하다.
성능이 높게 나와서 좋지만. 내가 잘사용하는 이 방법이 정말 좋은 것인지는 아직 잘모르겠다.
댓글
댓글 쓰기