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

Ответ 1

Алгоритм:

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

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

Анализ:

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

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

Ответ 2

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

Ответ 3

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

ИЗМЕНИТЬ: Еще одно замечание, похоже, вопрос заключается в том, чтобы задать вам наибольшее расстояние между любыми номерами, которые я не понял, когда я написал код. Чтобы исправить это, вам просто нужно создать словарь или массив (если вы знаете диапазон чисел, которые могут существовать), для хранения коллекций 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;
}

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

Ответ 4

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

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

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

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

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

ИЗМЕНИТЬ

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

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

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

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

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

Ответ 5

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