5

質問: N 個の整数 [N<=10^5] が与えられた場合、差が K [K>0 および K<1e9] である整数のペアの合計を数えます。N 個の整数のそれぞれは 0 より大きく、2^31-1 から少なくとも K 個離れています (すべて 32 ビット整数で行うことができます)。

1 行目には N と K (整数) が含まれます。2 行目には N 個の集合が含まれています。N 個の数はすべて異なることが保証されます。

ハッカーランクからの質問です。質問の解決策を見つけましたが、すべてのサンプル テスト ケースの制限時間を満たしていません。別のアルゴリズムを使用できるかどうかはわかりませんが、アイデアがありません。誰かが私のコードをチェックしてヒントを1つか2つ与えるために少し時間を割いてくれたら本当に感謝します.

temp = input()
temp = temp.split(" ")
N = int(temp[0])
K = int(temp[1])
num_array = input()
num_array = num_array.split(" ")
diff = 0
pairs= 0
i = 0
while(i < N):
    num_array[i] = int(num_array[i])
    i += 1
while(num_array != []):    
    j = 0
    while(j < (len(num_array)-1)):
        diff = abs(num_array[j+1] - num_array[0])
        if(diff == K):
            pairs += 1
        j += 1
    del num_array[0]
    if(len(num_array) == 1):
        break
print(pairs)
4

2 に答える 2

5

次の手順に従って、ほぼ線形時間でこれを行うことができます。

したがって、O(n) ソリューション:

  1. 各数値 x について、ハッシュセット H[x] に追加します
  2. 各数値 x について、xk が H に含まれているかどうかを確認し、含まれている場合は 1 を加えて答えます

または、O(nlgn) でバランスの取れた構造 (ツリーベースのセットなど) を使用することによって

このソリューションは、整数が異なるという仮定に基づいています。そうでない場合は、要素が「セットに追加」された回数を格納する必要があり、答えに 1 を追加する代わりに、H[x]*H[ の積を追加します。 x+k]

したがって、一般に、「デフォルト値0」の HashMap H を使用します

  1. 数値 x ごとにマップを更新: H[x] = H[x]+1
  2. 数値 x ごとに、答え H[x]*H[xk] に追加します (マップに含まれているかどうかを確認する必要はありません。含まれていない場合は H[xk]=0 です)。

もう一度-ハッシュマップを使用したソリューションはO(n)であり、ツリーマップO(nlgn)を使用しています

したがって、数値 A のセットと数値 k (個別の数値の解) が与えられます。

H=set()
ans=0
for a in A: 
  H.add(a)
for a in A: 
  if a-k in H: 
    ans+=1
print ans

またはそれより短い

H=set(A)
ans = sum(1 for a in A if a-k in H)
print ans
于 2013-10-27T14:15:48.633 に答える