高效算法用於在陣列

Question

例如計數對相同的元件的數量，

int num[] = {1, 5, 3, 12, 5, 1, 4}; 
int len = 7; 
int count = 0; 

（假設有不大於陣列中的相同的元件的2）
然後，我會做

for(int i=0; i<len-1; i++) { 
    for(int j=i+1; j<len; j++) { 
    if(num[i] == num[j]) { 
     count++; 
    } 
    } 
} 

然後計數爲2。

但爲O的效率（N^2），該算法的結果。
有沒有更高效的方法？
預先感謝您！

Answer 1

比O(n log n)更快，使用hash table。其結構爲線性或O(n);每次插入時，當您遍歷輸入數組時，您可以測試（如果在您的散列表中已經存在該密鑰）（即，「對」），您可以測試（使用常量，成本爲O(1)）。當你發現這個「匹配」的情況下，你增加一個計數器。一旦你完成了陣列，你的櫃檯就會告訴你答案。

Answer 2

你可以試試這個方法：

#define MAX 99999 // consider your array have largest elemnt < 99999 and >=0 
    int main() { 
    int num[] = {1, 5, 3, 12, 5, 1, 4,3}; 
    int len = 8; 
    int count[MAX+1u] = {0}; 
    int i,pair=0; 
    for(i=0;i<len;i++){ 
     count[num[i]]++; // here count the frequecy of each number 
    } 
    for(i=0;i<MAX;i++){ 
    if(count[i]>1){    // if frequecy is > 1  
    printf("%d occurs %d times \n",i,count[i]); 
    pair++;   // increment pair 
    } 

    } 
    printf("%d pairs ",pair); // print pair 
     return 0; 
    } 

Answer 3

基本上，其核心思想是一樣的：你要算在你的輸入數組每個元素的出現次數的數量。

關鍵問題是如何實現這個計數過程。你的解決方案是完全有效的，但正如你感覺到的那樣，它可以得到改進。 您收到了一條評論，建議對數組進行排序，然後對其執行掃描以計算對數：O（n.ln n）。

您也可以使用哈希表，正如@AlexReynolds的答案所建議的。但是你必須處理碰撞，因爲不同的整數可能會散列到同一個鍵上。爲此，您可以爲每個密鑰使用一個存儲桶。這個桶將存儲散列到其密鑰的每個整數，加上所述整數的出現次數。

如何實現這些桶：

• 隨着列表？如果你碰到一些碰撞，這就足夠了。
• With 堆（如二進制堆）：對數訪問和插入，但固定大小，如果碰撞發生太多，您可能需要重新分配。如果您不低估碰撞次數，但如果高估了內存，則會增加內存使用量。
• With 平衡二叉樹：對數查找和插入，但由於指針跟蹤在「內部」進行而造成的空間開銷。但在這裏，您避免了誘導的堆積的估計問題。

一旦你的哈希表建立，出現在你的數組中的每個元素的出現，你必須計數對。但你可以保留一個計數器，同時填充數據結構以避免執行這種額外的掃描。這很容易。下面是使用元素Ë從陣列中採取更新表格的基本操作：

1. 哈希è：我們得到了一個哈希鍵ķ
2. 獲取散列鍵鬥ķ：b
3. 擡頭望鬥，看是否ê是在那裏：
   • 如果是這樣：增加元素出現計數器。 如果計數器爲2，則遞增計數器對，如果計數器爲3，則遞減計數器對。
   • 如果不是：該元素添加到桶中，與發生計數器設置爲1
4. 獲取ë輸入數組中的下一個元素並且重複，直到該數組已完全sweeped。

正在執行一個如果聲明比到底執行一個簡單的檢查速度更快各計數器更新？我不確定，只是知道你可以測試兩者。

讓k是哈希表中的槽數。使用均勻分佈的散列函數，每個插槽將獲得n/k個元素。這導致列表中的n 2/k時間複雜度，其爲O（n 2）... 但是如果k接近於n你實際上接近線性時間。

對於堆/樹桶也是如此，除非最終得到O（n。ln n）漸近複雜度。如果k足夠大，再次，你將接近線性時間。

Answer 4

你不能使用正常的哈希表。我使用動態編程和散列表。

你必須讓你的哈希表是這樣的：

[數組的值，重複數，相同的對數]

例如，我們可以在陣列A = [3, 3, 3, 3, 3]上運行我的算法。

我們走過Array。用於在第一數目，所述新的行被插入到哈希表

3,0,0 /* A[i], the number of repetition of 3 so far (Rep[i]), 
        the number of identical pair so far (Iden[i]). */ 

然後第二3中所述的：

3,1,1 

第三3中所述的：

3,2,3 

爲第四3中A：

3,3,6 

6是id的個數在這個數組中的真正對。一般情況下，我們可以通過以下公式計算相同對數：

鑑定者[I] =代表[I] +鑑定者[I-1]

下面是在C＃代碼示例：

 public static int solution(int[] A) 
    { 
     int identical = 0; 
     Dictionary<int, KeyValuePair<int, int>> dic = new Dictionary<int, KeyValuePair<int, int>>(); /* A[i], the number of repetition of 3 so far (Rep[i]), 
        the number of identical pair so far (Iden[i]). */ 
     for (int i = 0; i < A.Length; i++) 
     { 
      if (!dic.ContainsKey(A[i])) 
       dic.Add(A[i], new KeyValuePair<int, int>(0,0)); 
      else 
      { 
       KeyValuePair<int,int> valDic = dic[A[i]]; 

       KeyValuePair<int, int> newVal; 
       if (valDic.Key < 1) 
        newVal = new KeyValuePair<int, int>(1, 1); 
       else 
       { 
        int preIdenticalPair = valDic.Value; 
        int preReptation = valDic.Key; 
        int newRepetation = ++preReptation; 
        int newIdenticalPair = preIdenticalPair + newRepetation; 
        newVal = new KeyValuePair<int, int>(newRepetation, newIdenticalPair); 
       } 

       dic[A[i]] = newVal; 
      } 
     } 

     //summation of all identical pairs 
     foreach (KeyValuePair<int, KeyValuePair<int, int>> pair in dic) 
      identical += pair.Value.Value; 
     return identical; 
    }