Наибольшее расстояние между равными числами в массиве

Question

скажем, у меня есть матрица (массив), как в этом примере, но гораздо больше:

</p> <pre><code>0 0 5 0 3 6 6 4 0 3 0 8 0 1 1 9 4 0 6 0 0 0 4 1 0 6 0 7 0 0 3 1 6 1 5 0 8 0 8 0 3 2 6 4 8 1 0 2 2 8 5 8 1 8 7 4 1 0 3 0 6 3 8 1 0 0 4 0 0 3 1 5 2 0 0 0 0 5 0 3 6 6 4 0 3 0 8 0 1 1 9 4 0 6 0 0 0 4 1 0 6 0 7 0 0 3 1 6 1 5 0 8 0 8 0 3 2 6 4 8 1 0 2 2 8 5 8 1 8 7 4 1 0 3 0 6 3 8 1 0 0 4 0 9 4 1 5 2 0 0

Я пытаюсь определить положение двух равных чисел с наибольшим расстоянием между ними в массиве по диагональной, горизонтальной или вертикальной прямой линии, причем расстояние рассчитывается как количество чисел между ними (расстояние d> = 0 ).

Другие ограничения:

• Прямая линия, как описано выше, может не содержать тот же номер, который обозначает ее начало и конец, поэтому вы не можете иметь 6 0 4 5 6 1 7 3 5 6 и, скажем, расстояние 6..6 равно 8, поскольку в последовательности есть 6.
• Номера для поиска не указаны, но должны определяться динамически.

В примере результата (рассматривая массив как обычную систему координат X | Y с 0, 0 в левом нижнем углу) он должен определить P1 (0, 8), P2 (8, 0) с d = 7 ( номер: 9).

Есть хорошие идеи о том, как сделать это эффективно? Я использую C #, но примеры / идеи на других языках тоже приветствуются.

В случае, если вам интересно, откуда возникает этот вопрос, я думал о различных математических задачах, которые, как мне кажется, трудно решить (для себя), и надеюсь лучше справиться с такими проблемами, увидев, как другие решают такие проблемы. проблемы. Спасибо!

Answer 1

Алгоритм:

Упростите проблему. Это эквивалентно решению одномерной версии (найти наибольшее расстояние между равными значениями в списке) один раз для строки, столбца и диагонали, а затем вернуть максимум.

Упростите больше. 1-мерная версия довольно проста. Вы просто создаете словарь, который отображает значения в список их позиций, решаете тривиальную задачу «какая наибольшая дельта в этом списке позиций» для каждого значения и возвращаете максимум.

Анализ:

Тривиальная задача занимает линейное время в размере списка позиций (поскольку список сортируется [по естественному порядку вставки]). Поэтому проблема 1-мерного разрыва занимает линейное время в размере списка значений (поскольку на одно значение приходится одна позиция). Следовательно, задача с 2-мерным промежутком занимает линейное время в размере матрицы (поскольку каждое значение входит ровно в четыре подзадачи с 1-кратным).

Таким образом, если матрица n m, решение займет O (n m) времени. Требуется пространство O (n + m) (для хранения словаря значений-> положений во время каждой 1-мерной фазы). Я действительно сомневаюсь, что у вас все получится лучше (время явно оптимальное, но не уверен насчет размера).

Answer 2

Основная идея следующего заключается в том, чтобы выполнить итерацию по массиву один раз, отслеживая последнее найденное местоположение в каждой строке (hor), столбце (vert) и диагонали сверху вниз (td) и диагонали снизу вверх ( дт). при этом вы просто находите расстояние до последнего места для каждого направления и берете макс.

EDIT : Еще одно замечание: похоже, вопрос состоит в том, чтобы просить вас определить наибольшее расстояние между одинаковыми числами, которое я не понял, когда писал код. Чтобы это исправить, вам просто нужно создать словарь или массив (если вы знаете диапазон чисел, которые могут существовать), чтобы хранить коллекции vert / hor / dt / td для каждого числа и использовать их вместо if yournum , Это все еще должно потребоваться только один раз через массив.

int findmax(int[,] myarray, int height, int width, int yournum)
{
int diagnum = width + height - 1;

int[] vert = new int[width];
int[] hor  = new int[height];

int[] td   = new int[diagnum];
int[] dt   = new int[diagnum];

for (int x = 0; x < width; x++)
{
   vert[x] = -1;
}
for (int x = 0; x < height; x++)
{
   hor[x] = -1;
}
for (int x = 0; x < diagnum; x++)
{
   td[x] = -1;
   dt[x] = -1;
}

int maxlen = 0;

for (int x = 0; x < width; x++)
{
   for (int y = 0; y < height; y++)
   {
      if (myarray[y,x] == yournum)
      {
         if (vert[x] == -1)
         {
            vert[x] = y;
         }
         else
         {
            maxlen = Math.Max(maxlen, Math.Abs(y - vert[x] - 1));
            vert[x] = y;
         }
         if (hor[x] == -1)
         {
            hor[x] = y;
         }
         else
         {
            maxlen = Math.Max(maxlen, Math.Abs(x - hor[y] - 1));
            hor[y] = x;
         }

         int tdcol = x - y + height - 1;
         int tdloc = Math.Abs(Math.Max(0, tdcol - height + 1) - x);
         if (td[tdcol] == -1)
         {
            td[tdcol] = tdloc;
         }
         else
         {
            maxlen = Math.Max(maxlen, Math.Abs(tdloc - td[tdcol] - 1));
            td[tdcol] = tdloc;
         }
         int dtcol = y + x;
         int dtloc = Math.Abs(Math.Max(0,dtcol-height+1) - x);
         if (dt[dtcol] == -1)
         {
            dt[dtcol] = dtloc;
         }
         else
         {
            maxlen = Math.Max(maxlen, Math.Abs(dtloc - dt[dtcol] - 1));
            dt[dtcol] = dtloc;
         }
      }
   }
}
return maxlen;
}

РЕДАКТИРОВАТЬ Я дважды проверил уравнения, но на самом деле не пытался построить / протестировать код, поэтому могут возникнуть некоторые проблемы компиляции или логические проблемы, но, похоже, это должно сработать. Основная часть состоит в том, чтобы получить правильные уравнения, что позволяет обходить необходимость многократно повторять массив (т.е. по одному на направление).

Answer 3

Я не понимаю, как вы можете сделать это действительно быстрее, кроме простой итерации по каждой строке, каждому столбцу и каждой диагонали (вы можете определить, находится ли что-то на одной диагонали, взяв абсолютное значение разности его X и координаты Y, конечно) и отслеживание самых последних координат каждого числа, которое вы видите, и наибольшего наблюдаемого разделения.

Answer 4

при условии, что расстояние должно быть прямым путем между двумя одинаковыми числами (т.е. без перекрестков с круговым движением или бесконечных петель).

1. создать массив из 10 (для цифры, которая появляется в проблеме)
   • DIGIT_STRUCT[10]
2. создать массив для каждой цифры для каждой позиции этой цифры. то есть образец всей сетки и упорядочить ее по номеру.
   • DIGIT_STRUCT[n].POSTITIONS[]
3. выбрать комбо из тех позиций, которые являются максимальным расстоянием
   • это сложная часть. но так как диагональные ходы разрешены, а таблица квадратная, я считаю, что вы можете ранжировать каждое сообщение по его расстоянию от начала координат (0,0). вам просто нужно выбрать первый и последний случай (по рангу). своего рода, для каждого списка цифр
   • DIGIT_STRUCT[n].MAX_DIST {POSITION a, POSITION b}
4. убедитесь, что хотя бы один минимальный путь для каждого MAX_DIST существует, не нажимая другой номер позиции. путь будет заблокирован только в том случае, если эта строка будет заполнена целой строкой или столбцом. в вашем 6 примере весь столбец заблокирован в подсетке другим 6.
5. сравнить каждую цифру максимального расстояния.

здесь не нужно выполнять всю работу, вам не нужно проверять пути, которые, очевидно, будут короче. если путь признан недействительным, вам не нужно искать другую позицию (сразу), если другая цифра содержит такой же путь.

если вы найдете потенциальный путь размера сетки (16 в вашем примере), вам следует просто попробовать и проверить его, так как другие не будут длиннее.

проверка пути должна потребовать двух массивов размера подсетки, hor и vert, добавить число к каждому vert [x] и hor [y] для каждого POSTITION (x, y) в DIGIT_STRUCT, который находится внутри подсетки. если не существует vert [n] или hor [m], равного размеру подсетки, вы знаете, что кратчайший путь там не будет заблокирован.

EDIT

забыл, что путь может быть неоптимальным. если существует такая ситуация, как

0 0 1 1
1 0 1 1
1 0 0 0
1 1 1 0

здесь ответ будет 0, путь = 6, от (0, 0) до (3, 3)

в этом случае вам придется проверять путь для каждого числа, и эта проверка должна возвращать расстояние. потому что расстояние пути может увеличиться, вам придется проверять намного больше путей для каждого числа (расстояние может быть не больше, чем в два раза).

Q. Вы вынуждены идти по самому прямому пути? в этом случае (квадратная подрешетка) существует только один прямой путь и он заблокирован. если вы вынуждены делать это, то я думаю, что вы можете получить некоторую производительность обратно, зная, что путь не увеличится во время проверки.

Answer 5

Поскольку вы ищете самый длинный «сегмент», начните поиск с максимально длинных сегментов и переходите к более коротким сегментам. Начав с большого конца, вы можете остановиться, как только найдете сегмент с соответствующими конечными числами. Это предполагает, что вам нужно вернуть только один сегмент, который длиннее ИЛИ РАВЕН любому другому сегменту.