在O（n）時間的數組中找到可分式總和對

-1

給出一個n整數a0, a1, .. an和一個正整數k的數組。查找和打印(i,j)對的數量，其中i+j可被k（即i+j % k == 0）均分。此問題已從here中取得。在O（n）時間的數組中找到可分式總和對

我們需要O(n)時間的解決方案。

一個解釋是，我們可以通過將元素分成桶來根據他們的模塊k來做到這一點。例如，你具備的要素：1 3 2 6 4 5 9 and k = 3

mod 3 == 0 : 3 6 9 
mod 3 == 1 : 1 4 
mod 3 == 2 : 2 5

然後，說：

現在，你可以對像這樣：與國防部3 == 0元素將匹配與元素（3 - 0）模K = 0，在MOD 3 == 0列表，以便其他元件，像這樣：（3,6）（3,9）（6,9）

此外：

將會有n *（n-1）/ 2個這樣的對，其中n是列表的長度，因爲列表是相同的並且i！= j。 mod 3 == 1的元素將與（3-1）mod k = 2的元素匹配，因此 mod 3 == 2列表中的元素如下所示：（1,2）（1,5）（4 ，2）（4，5）

它是有道理的(3, 6) (3, 9) (6, 9) (all items in the 0th bucket be paired)自(a + b)% k = 0 = a % k + b % k。

什麼是不明確的是，其他對是如何通過組合第一（mod 3 == 1）和第二（mod 3 == 2）桶中的元素生成的，爲什麼會有n *（n - 1）/ 2對。是否有另一種（更好）的方法？

這個問題適用於Math Stackexchange，這個問題在發佈問題之前並不知曉。

來源

2016-07-15 FlyingAura

恕我直言，這不是一個Python相關的問題，但數學。 –

「然後它說：」 - *其中*是以下文字說的？我沒有看到它， –

你沒有列出我

您有n * (n - 1)/2雙，因爲每個人（n）都可以與其他人配對（n-1）;但由於順序無關緊要，所以我們避免將鏡像對除以二。

當分子相加時，同一商的餘數相加，但提示不能超過商。在3的劃分中提醒3實際上是0的提醒。

答案是非常聰明的，你可以使它在低級別優化中快幾個百分點;例如實現專用的模塊3而不是依靠%的通用算法;但是你不可能擊敗O(n)，因爲你需要掃描每個元素至少一次，並且解決方案已經不再做太多了。（實際上，因爲你被要求寫的結果，在我看來，你不能在低於O(n^2)，正因爲如此... ...）

這些問題都與python沒有任何關係。你知道嗎有math.stackexchange.com？

來源

2016-07-15 13:36:46

我不知道數學堆棧交換，這個問題應該在那裏。感謝那些信息 – FlyingAura

我翻譯的C代碼...

using namespace std; 
int main(){ 

    int n; 
    int k; 
    cin >> n >> k; 
    int a[n]; 
    int m[k]; 
    for(int i=0; i<k; i++) 
     m[i]=0; 
    for(int i = 0; i < n; i++){ 
     cin >> a[i]; 
     m[a[i]%k]++; 
    } 
    int sum=0; 
    sum+=(m[0]*(m[0]-1))/2; 
    for(int i=1; i<=k/2 && i!=k-i; i++){ 
     sum+=m[i]*m[k-i]; 
    } 
    if(k%2==0) 
     sum+=(m[k/2]*(m[k/2]-1))/2; 
    cout<<sum; 
    return 0; 
}

成Python：

def divisible_sum_pairs(n, k, a_list): 
    m = [0] * len(a_list) 
    for a in a_list: 
     m[a % k] += 1 

    sum = int(m[0] * (m[0] - 1)/2) 
    for i in range(1, int(k/2) + 1): 
     if i != k - 1: 
      sum += m[i] * m[k - i] 
    if k % 2 == 0: 
     sum += m[int(k/2)] * (m[int(k/2)] - 1)/2 

    return sum

有了：

print(divisible_sum_pairs(6, 3, [1, 3, 2, 6, 1, 2]))

你得到5

來源

2016-07-15 13:48:41

我的意圖不是擁有代碼，而是背後的邏輯。不過謝謝你，這也有幫助。 – FlyingAura

在O（n）時間的數組中找到可分式總和對

回答

相關問題