可以選擇數字對的最快算法

問題：給定N個整數[N < = 10^5]，計算總差異數爲K的整數對。[K> 0和K < 1e9]。 N個整數中的每一個將大於0並且至少K距離2^31-1（一切都可以用32位整數完成）。可以選擇數字對的最快算法

第一行包含N & K（整數）。第二行包含N組數字。所有的N號碼都是有保證的。

現在的問題來自hackerrank。我得到了一個問題的解決方案，但它不符合所有樣本測試用例的時間限制。我不確定是否有可能使用另一種算法，但我沒有想法。如果有人花了一點時間檢查我的代碼並給出一兩個提示，我會非常感激。

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)

來源

2013-10-27 Nwaiwu Gilbert

可以通過以下的方法在aproximately線性時間做到這一點：

因此，O（n）的溶液：

對於每個數x將其添加到散列集H [ X]
對於每個編號X檢查XK是否是H，如果是 - 加1回答

，或者使用幾類b寵辱不驚結構（如基於樹的集）在O（nlgn）

假設該解決方案鹼基整數是不同，如果他們不是你需要存儲已補充說：「次元的數量來設定「和而不是添加1回答 - 添加的H [X] * H [X + K]

所以一般你採取一些HashMap的高帶產品」默認值0「

對於每個號碼x更新地圖：H [x] = H [x] +1
對於每個數字x添加到答案H [x] * H [xk]不需要檢查它是否在地圖中，因爲如果它不是，H [xk] = 0）

並且再次 - 使用散列映射的解決方案是O（n）並使用樹映射O（nlgn）

所以給定numbesr 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-27 14:15:48 lejlot

好的。問題是如果你有一系列給定的值，找出有差異k的數對的總數。例如。如果你有5個數字：1 3 5 2 7 ...和k = 2，這兩對是：（1,3）（3,5）（5,7）。在我的情況下，我檢查第一個數字（在上面的例子中，「1」）與所有其他數值。如果存在差異，我將1加到最終答案中。然後對下一個值做相同的操作（省略之前檢查的數字）。你能解釋你的方式好一點嗎？ –

@Nwaiwu - 在這裏沒有什麼可以解釋的 - 建議的方法是通過每個項目並檢查是否存在任何差異「k」的項目。整個「訣竅」是可以在恆定時間（使用散列集）而不是線性時間（通過循環 - 如在您的解決方案中）執行此檢查。 – lejlot

@lejlot：非常感謝。有效：）。還有一件事：你的意思是「可以在恆定時間（使用散列集）而不是線性時間（通過循環 - 如在你的解決方案中）」來完成。我之前沒有在python中使用set（），所以它的速度如何呢？ –

使用字典（散列映射）。

步驟1：填充字典D與數組中的所有條目。第2步：計算詞典中所有A [i] + k的出現次數。

Dictionary<int> dict = new Dictionary<int>(); 
foreach (int n in num_array) do dict.Add(n); 
int solitions = 0; 
foreach (int n in num_Array) do 
    if dict.contains(n+k) 
    solutions += 1;

填寫字典是O（1），搜索也是O（1）。爲數組中的每個元素做O（n）。這是儘可能快的。

不好意思，你必須把它翻譯成python。

編輯：與前一個想法相同。很抱歉發佈重複。我猜想刪除我的重複已經太晚了。

來源

2013-10-27 14:28:53 alzaimar

你可以**總是**刪除你自己的答案 – lejlot

可以選擇數字對的最快算法

回答

相關問題