Сравните все элементы внутри 2D-массива друг с другом

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), использующим списки, является создание массива H из n + 1 целых чисел, инициализированных до -1; также выделяют массив L из m целых чисел каждый, чтобы использовать их как элементы списка. Для элемента i 'th, со значением A [i], установите k = A [i] и L [i] = H [k] и H [k] = i. Когда это будет сделано, каждый H [k] является заголовком списка записей с равными значениями в них. Для 2D-массивов обработайте элемент массива A [i, j] как A [i + n * (j-1)].

Вот пример Python с использованием списков питона с п = 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.