比較二維數組中的所有元素互相之間

Question

我有一個完美的正方形64x64二維整數數組，它永遠不會超過64的值。我想知道是否有一種非常快速的方法來比較所有的元素並以獨特的方式顯示相同的內容。

在當前時刻我有這個

2D int array named array 
loop from i = 0 to 64 
    loop from j = 0 to 64 
     loop from k = (j+1) to 64 
      loop from z = 0 to 64 
       if(array[i][j] == array[k][z]) 
        print "element [i][j] is same as [k][z] 

正如你看到的有4個嵌套循環的是，我想不使用相當愚蠢的事。語言無論如何都不重要，我只是好奇地想知道可以使用哪種酷解決方案。由於任何整數內的值不會大於64，所以我猜你只能使用6位並將數組轉換爲更有趣的東西。因此，這將需要更少的內存，並允許一些真正花式的按位操作。唉，我並不是非常瞭解這種格式，所以想看看你們能想出什麼。

感謝任何人事先提供一個真正獨特的解決方案。

Answer 1

沒有必要通過O（m log m）算法對數組進行排序;您可以使用O（m）桶排序。 （設m = n * n = 64 * 64）。使用列表的簡單O（m）方法是設置n + 1個整數的數組H，初始化爲-1;還要分配一個數組L，每個整數爲m，用作列表元素。對於i的第th個數組元素，其值爲A [i]，設置k = A [i]並且L [i] = H [k]並且H [k] = i。完成後，每個H [k]是其中具有相同值的條目列表的頭部。對於二維數組，將數組元素A [i，j]視爲A [i + n *（j-1）]。

下面是一個Python的例子使用python列表，其中n = 7爲了便於觀察結果：

import random 
n = 7 
m = n*n 
a=[random.randint(1,n) for i in range(m)] 
h=[[] for i in range(n+1)] 
for i in range(m): 
    k = a[i] 
    h[k].append(i) 
for i in range(1,n+1): 
    print 'With value %2d: %s' %(i, h[i]) 

它的輸出看起來像：

With value 1: [1, 19, 24, 28, 44, 45] 
With value 2: [3, 6, 8, 16, 27, 29, 30, 34, 42] 
With value 3: [12, 17, 21, 23, 32, 41, 47] 
With value 4: [9, 15, 36] 
With value 5: [0, 4, 7, 10, 14, 18, 26, 33, 38] 
With value 6: [5, 11, 20, 22, 35, 37, 39, 43, 46, 48] 
With value 7: [2, 13, 25, 31, 40] 

Answer 2

在數組上使用quicksort，然後迭代數組，存儲「遊標」的臨時值（您正在查看的當前值），並確定臨時值是否與下一個遊標相同。

array[64][64]; 
quicksort(array); 
temp = array[0][0]; 
for x in array[] { 
    for y in array[][] { 
     if(temp == array[x][y]) { 
      print "duplicate found at x,y"; 
     } 
     temp = array[x][y]; 
    } 
} 

Answer 3

class temp { 
    int i, j; 
    int value; 
} 

然後填寫你的數組類臨時數組[64] [64]，然後按值排序（您可以通過實現可比接口做到這一點在Java中）。然後，相等的元素應該彼此相繼，並且可以爲彼此提取i，j。

該解決方案將是最優化的，歸類爲big-O notation的二次方法。