ソート配列から特定数の[Zohoインタビュー]を取得する
1323 ワード
🤢 質問する
N個の要素を含む数列を昇順に並べます.このとき、この数列にxが現れる回数を計算してください.例えば、数列[1,1,2,2,2,3]にx=2がある場合、現在の数列には4つの値が2の要素があるため、4が出力される.
しかし,アルゴリズムを時間複雑度O(logn)として設計しなかった場合,この問題は「タイムアウト」と判定される.の第1行において、Nおよびxは整数で区切られて入力される.
(1 <= N <= 1,000,000), (-10^9 <= x <= 10^9) 行目に入力されたN個の要素は、整数でスペースで区切られています.
(-10^9<=各要素の値<=10^9) 列の要素から、出力値がxの要素数です.要素値がxでない場合は、-1が出力されます.
N個の要素を含む数列を昇順に並べます.このとき、この数列にxが現れる回数を計算してください.例えば、数列[1,1,2,2,2,3]にx=2がある場合、現在の数列には4つの値が2の要素があるため、4が出力される.
しかし,アルゴリズムを時間複雑度O(logn)として設計しなかった場合,この問題は「タイムアウト」と判定される.
입력 조건(1 <= N <= 1,000,000), (-10^9 <= x <= 10^9)
(-10^9<=各要素の値<=10^9)
출력 조건입력 예시1 7 2
1 1 2 2 2 2 3출력 예시 1 4입력 예시 2 7 4
1 1 2 2 2 2 3출력 예시 2 -1n,x = map(int, input().split())
array = list(map(int, input().split()))
def binary_search(start, end, target, sum):
while start<=end:
mid = (start + end) // 2
if mid == 7:
return sum
if array[mid] == target:
sum += 1
del array[mid]
return sum
elif array[mid] < target:
start = mid + 1
else:
end = mid - 1
return sum
sum=0
for i in array:
sum = binary_search(0, n, x, sum)
if sum == 0:
print(-1)
else:
print(sum)Reference
この問題について(ソート配列から特定数の[Zohoインタビュー]を取得する), 我々は、より多くの情報をここで見つけました https://velog.io/@hyesoup/Zoho-인터뷰-정렬된-배열에서-특정-수의-개수-구하기テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol