Как мне найти номер в 2d массиве, отсортированном слева направо и сверху вниз?

Question

Мне недавно дали этот вопрос на собеседовании, и мне любопытно, каким будет хорошее решение.

Скажем, мне дали 2d массив, где все числа в массиве увеличиваются порядок слева направо и сверху Дно.

Каков наилучший способ поиска и определить, находится ли целевое число в массив

Теперь я хочу использовать бинарный поиск, так как мои данные отсортированы. Я могу определить, находится ли число в одной строке за O (log N) времени. Однако, это два направления, которые сбивают меня с толку.

Другое решение, которое, как я думал, может сработать, - начать где-то посередине. Если среднее значение меньше, чем моя цель, то я могу быть уверен, что оно находится в левой квадратной части матрицы от середины. Затем я двигаюсь по диагонали и снова проверяю, уменьшая размер квадрата, в котором потенциально может находиться цель, пока я не отточу целевое число.

У кого-нибудь есть хорошие идеи по решению этой проблемы?

Пример массива:

Сортировка слева направо, сверху вниз.

1  2  4  5  6  
2  3  5  7  8  
4  6  8  9  10  
5  8  9  10 11  

Answer 1

public boolean searchSortedMatrix(int arr[][] , int key , int minX , int maxX , int minY , int maxY){

    // base case for recursion
    if(minX > maxX || minY > maxY)
        return false ;
    // early fails
    // array not properly intialized
    if(arr==null || arr.length==0)
        return false ;
    // arr[0][0]> key return false
    if(arr[minX][minY]>key)
        return false ;
    // arr[maxX][maxY]<key return false
    if(arr[maxX][maxY]<key)
        return false ;
    //int temp1 = minX ;
    //int temp2 = minY ;
    int midX = (minX+maxX)/2 ;
    //if(temp1==midX){midX+=1 ;}
    int midY = (minY+maxY)/2 ;
    //if(temp2==midY){midY+=1 ;}


    // arr[midX][midY] = key ? then value found
    if(arr[midX][midY] == key)
        return true ;
    // alas ! i have to keep looking

    // arr[midX][midY] < key ? search right quad and bottom matrix ;
    if(arr[midX][midY] < key){
        if( searchSortedMatrix(arr ,key , minX,maxX , midY+1 , maxY))
            return true ;
        // search bottom half of matrix
        if( searchSortedMatrix(arr ,key , midX+1,maxX , minY , maxY))
            return true ;
    }
    // arr[midX][midY] > key ? search left quad matrix ;
    else {
         return(searchSortedMatrix(arr , key , minX,midX-1,minY,midY-1));
    }
    return false ;

}

Answer 2

Оптимальное решение - начать с левого верхнего угла, который имеет минимальное значение. Перемещайтесь по диагонали вниз вправо, пока не дойдете до элемента, значение которого> = значение данного элемента. Если значение элемента равно значению данного элемента, возвращаемое значение найдено как true.

В противном случае отсюда мы можем действовать двумя способами.

Стратегия 1:

1. Двигайтесь вверх по столбцу и ищите заданный элемент, пока не дойдете до конца. Если найдено, вернуть найдено как true
2. Двигайтесь влево в строке и ищите данный элемент, пока не дойдете до конца. Если найдено, вернуть найдено как true
3. возврат найден как ложный

Стратегия 2: Пусть i обозначает индекс строки, а j обозначает индекс столбца диагонального элемента, на котором мы остановились. (Здесь мы имеем i = j, кстати). Пусть k = 1.

• Повторяйте следующие шаги, пока i-k> = 0
  1. Поиск, если a [i-k] [j] равен данному элементу. если да, возвращаемое значение найдено как истинное
  2. Поиск, если a [i] [j-k] равен данному элементу. если да, возвращаемое значение как верное
  3. Инкремент k

1 2 4 5 6
2 3 5 7 8
4 6 8 9 10
5 8 9 10 11

Answer 3

Поскольку это вопрос интервью, это может привести к обсуждению Параллельного программирования и алгоритмов Map-Reduction .

См. http://code.google.com/intl/de/edu/parallel/mapreduce-tutorial.html

Answer 4

У меня есть рекурсивное решение «Разделяй и властвуй». Основная идея для одного шага заключается в следующем: мы знаем, что левый верхний (LU) наименьший, а правый нижний (RB) самый большой номер, поэтому данное No (N) должно: N> = LU и N <= RB </p>

ЕСЛИ N == LU и N == RB :::: Элемент найден и отмена возврата позиции / индекса Если N> = LU и N <= RB = FALSE, No не существует и прерывается. Если N> = LU и N <= RB = TRUE, разделите 2D-массив на 4 равные части 2D-массива в каждой логической форме. А затем примените один и тот же шаг алгоритма ко всем четырем подмассивам. </p>

Мой алгоритм верен. Я реализовал это на ПК моих друзей. Сложность: каждые 4 сравнения могут быть использованы для вывода общего количества элементов до одной четвертой в худшем случае. Моя сложность составляет 1 + 4 x lg (n) + 4 Но действительно ожидал, что это будет работать на O (n)

Я думаю, что-то не так в моем расчете сложности, пожалуйста, исправьте, если так ..

Answer 5

Ну, для начала давайте предположим, что мы используем квадрат.

1 2 3
2 3 4
3 4 5

1. Поиск квадрата

Я бы использовал бинарный поиск по диагонали. Цель состоит в том, чтобы найти меньшее число, которое не строго ниже целевого числа.

Скажем, я ищу, например, 4, тогда я в конечном итоге найду 5 в (2,2).

Тогда я уверен, что если 4 находится в таблице, он находится на позиции либо (x,2), либо (2,x) с x в [0,2]. Ну, это всего лишь 2 бинарных поиска.

Сложность не пугающая: O(log(N)) (3 бинарных поиска по диапазонам длины N)

2. Поиск прямоугольника, наивный подход

Конечно, становится немного сложнее, когда N и M различаются (прямоугольником), рассмотрим этот вырожденный случай:

1  2  3  4  5  6  7  8
2  3  4  5  6  7  8  9
10 11 12 13 14 15 16 17

И, скажем, я ищу 9 ... Диагональный подход все еще хорош, но определение диагонали меняется. Здесь моя диагональ [1, (5 or 6), 17]. Допустим, я взял [1,5,17], тогда я знаю, что если 9 находится в таблице, то это либо в подразделе:

            5  6  7  8
            6  7  8  9
10 11 12 13 14 15 16

Это дает нам 2 прямоугольника:

5 6 7 8    10 11 12 13 14 15 16
6 7 8 9

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

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

• Применить бинарный поиск к 10 11 12 13 14 15 16, не найдено
• Применить бинарный поиск к 5 6 7 8, не найдено
• Применить бинарный поиск к 6 7 8 9, не найдено

Это сложно, потому что для получения хорошей производительности вы можете различать несколько случаев в зависимости от общей формы ....

3. В поисках прямоугольника, жестокий подход

Было бы намного проще, если бы мы имели дело с квадратом ... так что давайте просто возьмем квадраты.

1  2  3  4  5  6  7  8
2  3  4  5  6  7  8  9
10 11 12 13 14 15 16 17
17 .  .  .  .  .  .  17
.                    .
.                    .
.                    .
17 .  .  .  .  .  .  17

Теперь у нас есть квадрат.

Конечно, мы, скорее всего, НЕ будем создавать эти строки, мы могли бы просто эмулировать их.

def get(x,y):
  if x < N and y < M: return table[x][y]
  else: return table[N-1][M-1]            # the max

так что он ведет себя как квадрат, не занимая больше памяти (за счет скорости, вероятно, в зависимости от кеша ... да ладно: p)

Answer 6

Бинарный поиск был бы лучшим подходом, imo. Начиная с 1/2 x, 1/2 y разрезает его пополам. То есть квадрат 5x5 будет выглядеть примерно так: x == 2 / y == 3. Я округлил одно значение вниз и одно значение до лучшей зоны в направлении целевого значения.

Для ясности следующая итерация даст вам что-то вроде x == 1 / y == 2 ИЛИ x == 3 / y == 5

Answer 7

Я предлагаю хранить все символы в 2D list.затем найдите индекс необходимого элемента, если он существует в списке.

Если его нет, напечатайте соответствующее сообщение, иначе выведите строку и столбец в виде:

row = (index/total_columns) и column = (index%total_columns -1)

Это приведет только к двоичному времени поиска в списке.

Пожалуйста, предложите любые исправления.:)

Answer 8

Если O (M log (N)) решение подходит для массива MxN -

template <size_t n>
struct MN * get(int a[][n], int k, int M, int N){
  struct MN *result = new MN;
  result->m = -1;
  result->n = -1;

  /* Do a binary search on each row since rows (and columns too) are sorted. */
  for(int i = 0; i < M; i++){
    int lo = 0; int hi = N - 1;
    while(lo <= hi){
      int mid = lo + (hi-lo)/2;
      if(k < a[i][mid]) hi = mid - 1;
      else if (k > a[i][mid]) lo = mid + 1;
      else{
        result->m = i;
        result->n = mid;
        return result;
      }
    }
  }
  return result;
}

Рабочая демонстрация C ++.

Пожалуйста, дайте мне знать, если это не сработает или если есть ошибка.

Answer 9

A. Выполните двоичный поиск в тех строках, где может быть указан целевой номер.

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