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

Ответ 1

False.

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

1 3 5
2 4 6
7 8 9

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

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

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

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

Ответ 2

O(k log(k)).

• Создайте миниатюру.

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

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

Ответ 3

Начните перемещение матрицы из верхнего левого угла (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;

}

Ответ 4

Как упоминалось ранее, самым простым способом является создание 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;
}

Ответ 5

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

Ответ 6

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

Ответ 7

//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];
}