K-й наименьший элемент в отсортированной матрице

Question

K-й наименьший элемент в отсортированной матрице

Это вопрос интервью.

Найдите K- ^й наименьший элемент в матрице с отсортированными строками и столбцами.
Верно ли, что самый маленький элемент K является одним из a[i, j] такие как i + j = K?

26

arrays algorithm matrix multidimensional-array data-structures

Источник

user521070 02 мар '13 в 21:17

8 ответов

Решение

O(k log(k)) решение.

Постройте мини-кучу.
добавлять (0,0) до кучи. Пока мы не нашли kth самый маленький элемент, удалите верхний элемент (x,y) из кучи и добавить следующие два элемента [(x+1,y) а также (x,y+1)] если они не были посещены раньше.

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

33

Источник

user1987143 23 сен '13 в 18:18

Эту проблему можно решить с помощью двоичного поиска и оптимизированного подсчета в отсортированной матрице. Бинарный поиск занимает O(log(n)) времени, и для каждого значения поиска требуется в среднем n итераций, чтобы найти числа, которые меньше искомого числа. Пространство поиска для двоичного поиска ограничено минимальным значением в матрице наmat[0][0] и максимальное значение mat[n-1][n-1].

Для каждого числа, выбранного из двоичного поиска, нам нужно подсчитать числа, которые меньше или равны этому конкретному числу. Таким образом $k^{th}$ можно найти наименьшее число.

Для лучшего понимания вы можете обратиться к этому видео:

https://www.youtube.com/watch?v=G5wLN4UweAM&t=145s

7

Источник

user13300532 19 апр '20 в 13:56

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

Реализация на Java:

private static class Cell implements Comparable<Cell> {

    private final int x;
    private final int y;
    private final int value;

    public Cell(int x, int y, int value) {
        this.x = x;
        this.y = y;
        this.value = value;
    }

    @Override
    public int compareTo(Cell that) {
        return this.value - that.value;
    }

}

private static int findMin(int[][] matrix, int k) {

    int min = matrix[0][0];

    PriorityQueue<Cell> frontier = new PriorityQueue<>();
    frontier.add(new Cell(0, 0, min));

    while (k > 1) {

        Cell poll = frontier.remove();

        if (poll.y + 1 < matrix[poll.x].length) frontier.add(new Cell(poll.x, poll.y + 1, matrix[poll.x][poll.y + 1]));
        if (poll.x + 1 < matrix.length) frontier.add(new Cell(poll.x + 1, poll.y, matrix[poll.x + 1][poll.y]));

        if (poll.value > min) {
            min = poll.value;
            k--;
        }

    }

    return min;

}

1

Источник

user504452 11 апр '15 в 23:55

Вы можете решить это за O(k) время, обходя диагонали матрицы от левого к верхнему правому краю. Тогда вам нужно только найти определенный k_1-й элемент на новой диагонали. Но это можно сделать не более чем за O(k) раз.

1

Источник

user9239839 19 июл '18 в 06:42

Как уже упоминалось ранее, самый простой способ - это min heap, Вот реализация Java с использованием PriorityQueue:

private int kthSmallestUsingHeap(int[][] matrix, int k) {

    int n = matrix.length;

    // This is not necessary since this is the default Int comparator behavior
    Comparator<Integer> comparator = new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o1 - o2;
        }
    };

    // building a minHeap
    PriorityQueue<Integer> pq = new PriorityQueue<>(n*n, comparator);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            pq.add(matrix[i][j]);
        }
    }

    int ans = -1;
    // remove the min element k times
    for (int i = 0; i < k; i++) {
        ans = pq.poll();
    }

    return ans;
}

1

Источник

user2517730 16 сен '16 в 20:25

Вышеупомянутое решение не могло обработать диагональное условие и не может быть применено к матрице ниже

int arr2[][] = { { 1, 4, 7, 11, 15 }, 
                 { 2, 5, 8, 12, 19 }, 
                 { 3, 6, 9, 16, 22 }, 
                 { 10, 13, 14, 17, 24 },
                 { 18, 21, 23, 26, 30 } }

И k=5

Возвращаю 7, а ответ 5

1

Источник

user2769629 30 окт '20 в 23:34

k ограничен n*m, Таким образом, решение, которое работает в O(k*log(k)) хуже чем O(k) что на самом деле O(n*m)Обыденный поиск.

0

Источник

user2736843 27 сен '13 в 11:40

K-й наименьший элемент в матрице:

Проблема может быть сужена, как показано ниже.

если k равно 20, тогда возьмите матрицу k*k (где ответ обязательно будет лежать.)

Теперь вы можете объединять строки в пару несколько раз, чтобы построить отсортированный массив, а затем найти k-е наименьшее число.

0

Источник

user3784101 28 апр '18 в 18:38

Кажется, это просто использует функцию: каждая строка сортируется, но не использует свою функцию сортировки по столбцам.

0

Источник

user753352 22 июл '14 в 04:04

//int arr[][] = {{1, 5, 10, 14},
//        {2, 7, 12, 16},
//        {4, 10, 15, 20},
//        {6, 13, 19, 22}
//};
// O(k) Solution
public static int myKthElement(int arr[][], int k) {
    int lRow = 1;
    int lCol = 0;
    int rRow = 0;
    int rCol = 1;
    int count = 1;

    int row = 0;
    int col = 0;

    if (k == 1) {
        return arr[row][col];
    }

    int n = arr.length;
    if (k > n * n) {
        return -1;
    }

    while (count < k) {
        count++;

        if (arr[lRow][lCol] < arr[rRow][rCol]) {
            row = lRow;
            col = lCol;

            if (lRow < n - 1) {
                lRow++;
            } else {
                if (lCol < n - 1) {
                    lCol++;
                }

                if (rRow < n - 1) {
                    lRow = rRow + 1;
                }
            }
        } else {
            row = rRow;
            col = rCol;

            if (rCol < n - 1) {
                rCol++;
            } else {
                if (rRow < n - 1) {
                    rRow++;
                }
                if (lCol < n - 1) {
                    rCol = lCol + 1;
                }
            }
        }
    }

    return arr[row][col];
}

-1

Источник

user4014066 22 мар '17 в 05:33

Другие вопросы по тегам arrays algorithm matrix multidimensional-array data-structures

user1204143 02 мар '13 в 21:28 2013-03-02 21:28 · Accepted Answer · 2013-03-02 21:28

Ложь.

Рассмотрим простую матрицу, подобную этой:

1 3 5
2 4 6
7 8 9

9 самый большой (9-й самый маленький) элемент. Но 9 в A[3, 3], а 3+3!= 9. (Независимо от того, какое соглашение об индексировании вы используете, оно не может быть истинным).

Вы можете решить эту проблему за O(k log n), постепенно объединяя строки, дополняя их кучей, чтобы эффективно найти минимальный элемент.

По сути, вы помещаете элементы первого столбца в кучу и отслеживаете строку, из которой они пришли. На каждом шаге вы удаляете минимальный элемент из кучи и помещаете следующий элемент из строки, из которой он получен (если вы достигнете конца строки, вы ничего не добавляете). Как удаление минимума, так и добавление нового элемента стоит O(log n). На j-м шаге вы удаляете jсамый маленький элемент, поэтому после k шаги, которые вы сделали за общую стоимость O(k log n) операции (где n - количество строк в матрице).

Для матрицы выше, вы изначально начинаете с 1,2,7 в кучу. Вы удаляете 1 и добавить 3 (так как первый ряд 1 3 5) получить 2,3,7, Вы удаляете 2 и добавить 4 получить 3,4,7, Удалить 3 и добавить 5 получить 4,5,7, Удалить 4 и добавить 6 получить 5,6,7, Обратите внимание, что мы удаляем элементы в глобально отсортированном порядке. Вы можете видеть, что продолжение этого процесса приведет к kнаименьший элемент после k итераций.

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