[Codility] MissingInteger

MissingInteger

初めての試み

def solution(A):
    # write your code in Python 3.6
    A = sorted(A)
    #print(A)
    idx = binary_search(A, 0, 0, len(A)-1)
    A = A[idx:]
    #print(A)
    if len(A) == 0:
        return 1
    if A[0] == 2:
        return 1
    for i in range(idx+1, len(A)):
        if A[i] - A[i-1] == 2:
            return A[i] - 1
    return A[len(A)-1] + 1
    #pass

def binary_search(arr, val, start, end):
    if start == end:
        if arr[start] > val:
            return start
        else:
            return start+1
 
    # this occurs if we are moving
    # beyond left's boundary meaning
    # the left boundary is the least
    # position to find a number greater than val
    if start > end:
        return start
 
    mid = (start+end)//2
    if arr[mid] < val:
        return binary_search(arr, val, mid+1, end)
    elif arr[mid] > val:
        return binary_search(arr, val, start, mid-1)
    else:
        return mid

うん...表現はいいですが、論理が間違っているようです.
しかし、コンパイルミスは間違いなく、幸いと言えます.

二次試行

def solution(A):
    # write your code in Python 3.6
    A = sorted(A)
    #print(A)
    idx = binary_search(A, 0, 0, len(A)-1)
    A = A[idx:]
    #print(A)
    if len(A) == 0:
        return 1
    if A[0] != 1:
        return 1
    for i in range(1, len(A)):
        if A[i] - A[i-1] >= 2:
            return A[i-1] + 1
    return A[len(A)-1] + 1
    #pass

def binary_search(arr, val, start, end):
    if start == end:
        if arr[start] > val:
            return start
        else:
            return start+1
 
    # this occurs if we are moving
    # beyond left's boundary meaning
    # the left boundary is the least
    # position to find a number greater than val
    if start > end:
        return start
 
    mid = (start+end)//2
    if arr[mid] < val:
        return binary_search(arr, val, mid+1, end)
    elif arr[mid] > val:
        return binary_search(arr, val, start, mid-1)
    else:
        return mid

問題をよく読みなさい.
どこにも連続した数字は書いていませんが、間違えました.
連続する数字の間にある数字を探していると思っていましたが...
[94,95,96]のような入力でもよい

複雑度は高いのですが、また間違えて、今回は1の沼に落ちてしまいました.

0を探して切るとこんなにも0がつかめない状況ですね!こいつを捕まえた.
今本当に当たったら.

3回目の試み

わあ成功~!

def solution(A):
    # write your code in Python 3.6
    A = sorted(A)
    #print(A)
    idx = binary_search(A, 0, 0, len(A)-1)
    A = A[idx:]
    #print(A)
    if len(A) == 0:
        return 1
    if A[0] != 1 and A[0] != 0:
        return 1
    for i in range(1, len(A)):
        if A[i] - A[i-1] >= 2:
            return A[i-1] + 1
    return A[len(A)-1] + 1
    #pass

def binary_search(arr, val, start, end):
    if start == end:
        if arr[start] > val:
            return start
        else:
            return start+1
 
    # this occurs if we are moving
    # beyond left's boundary meaning
    # the left boundary is the least
    # position to find a number greater than val
    if start > end:
        return start
 
    mid = (start+end)//2
    if arr[mid] < val:
        return binary_search(arr, val, mid+1, end)
    elif arr[mid] > val:
        return binary_search(arr, val, start, mid-1)
    else:
        return mid