算法 - 計算O（n）中排序數組中所有對數相等的數？

Question

我猜測的一個問題如下：

比方說，我們有一個排序數組{1,1,1,1,2,2,4,4,4}。

現在，鑑於我們可以清楚地看到，我們有1對6對，1對2和3對4對（10對）。你將如何構造一個在O（n）中找到這些對的算法？

我已計數在一個陣列的對並且這樣做這樣的算法：

Arrays.sort(array); 
 
int counter = 0; 
 
for(int i = 0; i<array.length; i++) { 
 
    for(int j = i+1; j<array.length; j++) { 
 
      if(j!=i && array[j] == array[i]) { 
 
\t counter++; 
 
\t } 
 
     } 
 
} 
 
return counter;

但這運行在O（N^2），我想（爲新手，我與算法），有一個更好的解決方案，以獲得相同的結果只使用一個for循環或多個while循環？

我想聽聽你的想法！

Answer 1

你可以做到這一點在O(N)：

int pairs = 0; 
int times = 1; 
for (int i = 1; i < array.length; ++i) { 
    if (array[i] == array[i-1]) { 
     ++times; 
    } else { 
     pairs += times*(times-1)/2; 
     times = 1; 
    }     
} 
pairs += times*(times-1)/2; 
return pairs;  

的Runnable：https://ideone.com/mu65ie

對於每一個不同的數，計算其出現times的數量。不同配對的數量等於選擇的數量C(times, 2) = times*(times-1)/2。

Answer 2

好了，這裏也是我的解決方案：

int i = 0; 
int pairs = 0; 

while (i < array.length - 1) { 
    if(array[i] == array[i + 1]) { 
     pairs += 1; 
     i += 2; 
    } else { 
     i++; 
    } 
} 

當一對被發現索引由兩個遞增，這使得遍歷快一點點。無論如何，複雜性是O(n)。

當然，你在數組爲sorted後運行這個。

Answer 3

如何：

Arrays.sort(array); 
    int counter = 0; 
    for(int i = 1; i<array.length; i++) { 
     if(array[i] == array[i-1]) { 
      counter++; 
      ++i; 
     } 
    } 
    return counter; 

Answer 4

的祕密是停止重申。緩存出現的數據。您可以使用緩存將其減少爲O（nlogn）問題。

對非常模糊的措辭，所以在未來的幾個更多的例子將澄清你不知道一個名字的東西，找到答案。您可以使用組合數學將問題簡化爲O（n）。

的wikipedia article有點鈍閱讀，但你正在尋找的公式是靠近頂部：

n!/(k! * (n - k)!) 

其中!表示階乘數，n表示項目相結合的量（ 4 1），k表示每個組合的項目數量（一對爲2）。因此，用這些值代替：

4! = 24 
2! = 2 
(4-2)! = 2 
4!/(2!2!) = 24/4 = 6 

使用這個方程式可以將其減少到O（n）。由於使用了階乘因子並對數據集進行了排序，因此可以通過緩存未來調用的階乘調用結果來進一步提高性能。幾何函數的排序輸入幾乎每個查找都會有緩存命中！

如果您使用python 3，緩存可能不是必需的，因爲它使用比python 2更高效的算法來計算階乘因子。緩存將減少冗餘，但是這可能會在非常大的值上產生很好的結果。

緩存（記憶化）的一個例子：

import math 

class Cache(object): 
    memos = dict() 

    def factorial(self, n): 
     if not n in self.memos: 
      self.memos[n] = math.factorial(n) 
     return self.memos[n]