[codility] 풀어보기 - PermMissingElem

Lesson 3-2  - PermMissingElem

내용 :

Find the missing element in a given permutation

시간 복잡도 : O(N)

성공 했지만 민망해서 공개 안하는 코드 : 

function isZero(element) {

return element == 1; } function solution(A) { // write your code in JavaScript (Node.js 6.4.0) let rt_arr=new Array(A.length+1); rt_arr.fill(1); for(i in A) { rt_arr[A[i]-1]=0; } //console.log(rt_arr.findIndex(isZero)+1); return rt_arr.findIndex(isZero)+1; }

기타 사항 :

• 코딜리티 레슨에 있던 댓글들이 사라짐
• 그래서 구글에서 찾아봤더니 역시나 좋은 코드들이 많이 나옴
• 참고용으로 소스 가져옴

def solution(A):     should_be = len(A) # you never see N+1 in the iteration     sum_is = 0       for idx in xrange(len(A)):         sum_is += A[idx]         should_be += idx+1       return should_be - sum_is +1 def solution(A):     missing_element = len(A)+1           for idx,value in enumerate(A):         missing_element = missing_element ^ value ^ (idx+1)               return missing_element

출처 : https://www.martinkysel.com/codility-permmissingelem-solution/

public int solution(int[] data) {

    long N = data.length + 1;

    long total = (N * (N + 1)) / 2;

    long sum = 0L;

    for (int i : data) {

        sum += i;

    }

    return (int)(total - sum);

}

출처 : https://codereview.stackexchange.com/questions/47471/perm-missing-elem-100-functional-score-but-only-60-performance

이건 나도 비슷하게 생각은 했는......