[Codility] MissingInteger
MissingInteger
うん...表現はいいですが、論理が間違っているようです.
しかし、コンパイルミスは間違いなく、幸いと言えます.
どこにも連続した数字は書いていませんが、間違えました.
連続する数字の間にある数字を探していると思っていましたが...
[94,95,96]のような入力でもよい
複雑度は高いのですが、また間違えて、今回は1の沼に落ちてしまいました.
0を探して切るとこんなにも0がつかめない状況ですね!こいつを捕まえた.
今本当に当たったら.
わあ成功~!
初めての試み
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
Reference
この問題について([Codility] MissingInteger), 我々は、より多くの情報をここで見つけました https://velog.io/@snusun/Codility-MissingIntegerテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol