Алгоритмы выбора по отсортированной матрице

Question

это вопрос об интервью Google:

Учитывая N * N Матрицу.Все строки отсортированы, а все столбцы отсортированы.Найти самый большой элемент K-й матрицы.

сделать это за n ^ 2 просто, и мы можем отсортировать его, используя сортировку по куче или слиянию (n lg n), а затем получить ее, но есть ли лучший подходлучше чем (n lg n)?

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

 1   5   7  12
 3   6   8  14
 4   9  10  15
11  17  19  20

1 <5 <7 <12 и 1 <3 <4 <11 аналогично другим строкам и столбцам,Теперь скажем, что нам нужно найти 10-й наименьший элемент, здесь он равен 11 .. надеюсь, это добавляет некоторые детали к вопросу ... </p>

Answer 1

Да, есть алгоритм O (K) из-за Фредериксона и Джонсона.

Грег Н. Фредериксон и Дональд Б. Джонсон. Обобщенный отбор и ранжирование: отсортированные матрицы . SIAM J. Comput. 13, с. 14-30. http://epubs.siam.org/sicomp/resource/1/smjcat/v13/i1/p14_s1?isAuthorized=no

Answer 2

С матрицей, приведенной в примере: Если вы хотите найти 7-й элемент, вы знаете, 7-й элемент находится в элементах M [4] [1..4], M [1 ..4] [4].Вы получаете два уже отсортированных массива: 12,14,15,20 и 11,17,19, которые можно объединить.Затем вы применяете двоичный поиск O (log N).

Обобщение: для k-го по величине элемента в этой матрице вы должны выбрать соответствующий слой: [2N-1] + [2 (N-1) -1] + ...> = k, поэтому алгоритм выбора подходящего слоя для поиска - Sum [2 (Ni) -1]> = k, для i = 0, N-1, где iномер слоя.После того как вы найдете номер слоя i, у вас будет 2 (Ni) -1 элемента в этом массиве, которые необходимо объединить, а затем искать.Сложность поиска в этом слое составляет O (log [2 (Ni) -1] = O (log (Ni)) ...

Арифметическая прогрессия приводит к

0> = i ^ 2-2 * N * i + k

i1,2 = N + -sqrt (N ^ 2-k), где k - элемент, который мы ищем ...

Answer 3

Ниже приведено мое решение на C ++, основанное на минимальной куче. Когда ячейка в матрице находится в верхней части минимальной кучи, число справа и / или снизу будет вставлено в кучу.

#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

struct Entry {
    int value;
    int x;
    int y;

    bool operator < (const Entry& other) {
        return this->value > other.value;
    }
};

bool getKthNumber(int* matrix, int row, int col, int k, int* result){
    if(matrix == NULL || row <= 0 || col <= 0 || result == NULL)
        return false;
    if(k <= 0 || k > row * col)
        return false;

    vector<Entry> minHeap;
    Entry first = {matrix[0], 0, 0};
    minHeap.push_back(first);
    make_heap(minHeap.begin(), minHeap.end());

    for(int i = 0; i < k; ++i){
        first = minHeap[0];
        int x = first.x;
        int y = first.y;
        if(first.y == 0 && first.x < row - 1){
            Entry next = {matrix[(x + 1) * col], x + 1, y};
            minHeap.push_back(next);
            push_heap(minHeap.begin(), minHeap.end());
        }
        if(first.y < col - 1){
            Entry next = {matrix[x * col + y + 1], x, y + 1};
            minHeap.push_back(next);
            push_heap(minHeap.begin(), minHeap.end());
        }

        pop_heap(minHeap.begin(), minHeap.end());
        minHeap.pop_back();
    }

    *result = first.value;
    return true;
}

Answer 4

Мой код ниже является алгоритмом O (k).Он не работает на определенном граничном случае (вероятно, по одному в каждом направлении: x и y).Я перечислил крайний случай, чтобы кто-то мог это исправить.Я не собираюсь это исправлять, потому что для меня это время ложиться спать.

Краткое описание алгоритма: вам нужно только отслеживать два кандидата #, которые могут быть наименьшими, один при движении в направлении xи один, продолжая в направлении у.Подумайте об этом, и это может иметь для вас смысл.

enum Direction {
  X,
  Y
};

struct Index
{
  Index(int unsigned x, int unsigned y)
    : x(x),
      y(y)
  {}

  void operator = (Index const & rhs)
  {
    x = rhs.x;
    y = rhs.y;
  }

  int unsigned x;
  int unsigned y;
};

int unsigned solve(int unsigned i_k, int unsigned ** i_data, int unsigned i_n)
{
  if (1 == i_k) {
    return i_data[0][0];
  }

  Direction dir = X;
  Index smaller(0,0);
  Index larger(0,0);

  if (i_data[1][0] < i_data[0][1]) {
    dir = X;
    smaller = Index(1,0);
    larger = Index(0,1); }
  else {
    dir = Y;
    smaller = Index(0,1);
    larger = Index(1,0);
  }

  for (int unsigned i = 0; i < (i_k - 2); ++i) {
    int unsigned const x = smaller.x;
    int unsigned const y = smaller.y;
    if (X == dir) {
      if ((x + 1) == i_n) {
        // End of row
        smaller = larger;
        larger.x += 1;
        dir = Y; }
      else if (i_data[x + 1][y] < i_data[larger.x][larger.y]) {
        smaller.x += 1; }
      else {
        smaller = larger;
        larger = Index(x + 1, y);
        dir = Y;
      } }
    else {
      if ((y + 1) == i_n) {
        // End of col
        smaller = larger;
        larger.y += 1;
        dir = X; }
      else if (i_data[x][y + 1] < i_data[larger.x][larger.y]) {
        smaller.y += 1; }
      else {
        smaller = larger;
        larger = Index(x, y + 1);
        dir = X;
      }
    }
  }
  return i_data[smaller.x][smaller.y];
}

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

  size = 4;
  data = createMatrix(size);
  data[0][0] = 1; data[1][0] = 6; data[2][0] = 10; data[3][0] = 11;
  data[0][1] = 3; data[1][1] = 7; data[2][1] = 12; data[3][1] = 14;
  data[0][2] = 4; data[1][2] = 8; data[2][2] = 13; data[3][2] = 15;
  data[0][3] = 5; data[1][3] = 9; data[2][3] = 19; data[3][3] = 20;
  answer = solve(14, data, size);
  assertAnswer(answer, 15, ++testNum);
  deleteMatrix(data, size);

Answer 5

Вы можете найти k ^th наименьший ожидаемый элемент времени O (n log n), если заметите, что:

1. Генерация случайного числа, которое лежит между Array [i] [j] и Array [k] [l], так что Array [i] [j]

Используя [1] в качестве подпрограммы, вы можете использовать процедуру, аналогичную RANDOMIZED-SELECT , чтобы сгенерировать k ^th наименьшее число во всем массиве.

Answer 6

Вы выполняете первый поиск дыхания, начиная с (0,0).(0,0) и 2 дочерних элемента (0,1) и (1,0) добавляются в список потенциальных кандидатов для 2-го элемента.Цикл, выбирающий наименьший элемент в списке потенциальных кандидатов в качестве следующего элемента, добавляет его дочерние элементы в список потенциальных кандидатов.Остановитесь, когда найдете k-й элемент.

Сделайте список потенциальных кандидатов минимальной кучей.Куча никогда не будет больше n + m.

Также вы можете сделать обратное с последнего элемента (n, m), если k больше, чем n * m / 2.

ХудСлучай: это будет n * m / 2 lg (n + m) вместо n * m lg (n * m) сортировки.

Answer 7

На основе N вы можете найти диагональ, в которой расположен элемент.Например, в матрице

 1   5   7  12
 3   6   8  14
 4   9  10  15
11  17  19  20

Вы можете вывести диагональ, определив общее количество элементов в предыдущих диагоналях,

/diagonal#/elements/# of elements/cumulative # of elements/
/d1/ 1         / 1 / 1 /
/d2/ 3 5       / 2 / 1+2 = 3 /
/d3/ 4 6 7     / 3 / 1+2+3 = 6 /
/d4/ 11 9 8 12 / 4 / 1+2+3+4 = 10 /
/d5/ 17 10 14  / 3 /
/d6/ 19 15     / 2 /
/d7/ 20        / 1 /

Причина, по которой нам нужно найти диагональэто потому, что диагонали выше всегда будут иметь элементы меньше, чем любой из текущих диагональных элементов, а диагонали ниже всегда будут иметь элементы больше, чем любой из текущих диагональных элементов.* имеет обязательный элемент (поскольку он содержит 7-й по 10-й по величине).Поскольку до предыдущей диагонали было 6 элементов, вам просто нужно найти 4-й по величине элемент в диагонали d4.

Answer 8

повернуть матрицу по часовой стрелке на 45 градусов.Вы получите набор данных в форме ромба.Высота будет 2N-1, количество элементов в каждом ряду сверху будет таким: 1,2,3,4,5,4,3,2,1 для N = 5

.узнайте, что каждое число в строке всегда больше любого числа выше.

для k-й строки (считая от 1), у вас будет k элементов для k = N k принадлежит {1..2N-1}

Вычисляя накопленное количество элементов от строки 1 до k-1 и от 1 до k, вы найдете строку, в которой находится ваша цель (сумма (1к k-1)

Теперь, когда вы нашли ряд элементов с наихудшим регистром N. Всего их можно отсортировать, а затем найти правильный.= sqrt (n), общая стоимость этого алгоритма составляет O (sqrt (n) ln (sqrt (n)))

Answer 9

Поскольку все уже отсортировано, вы можете просто выполнить поиск по диагонали. (Хотя, честно говоря, я не знаю, что это означает, что & ldquo; все строки отсортированы, а все столбцы отсортированы & rdquo ;. Если это действительно так, то просто перейдите к k-му элементу в диагональном перечислении матрицы.)