Двоичный поиск для решения «K-й наименьший элемент в отсортированной матрице». Как можно убедиться в правильности алгоритма,

Я имею в виду вопрос leetcode: Kth Наименьший Элемент в отсортированной матрице

Есть два известных решения проблемы. Один использует Heap/PriorityQueue, а другой использует двоичный поиск. Решение для двоичного поиска выглядит следующим образом (верхнее сообщение):

public class Solution {
public int kthSmallest(int[][] matrix, int k) {
    int lo = matrix[0][0], hi = matrix[matrix.length - 1][matrix[0].length - 1] + 1;//[lo, hi)
    while(lo < hi) {
        int mid = lo + (hi - lo) / 2;
        int count = 0,  j = matrix[0].length - 1;
        for(int i = 0; i < matrix.length; i++) {
            while(j >= 0 && matrix[i][j] > mid) j--;
            count += (j + 1);
        }
        if(count < k) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}
}

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

Поскольку область поиска представляет собой min и max значения массива, mid НЕ обязательно должно быть значением, которое находится в массиве. Однако возвращаемый lo всегда есть.

Почему это происходит?


whiteboard binary-search
person Snehasis Ghosh    schedule 10.03.2018    source источник

Ответы (2)


arrow_upward
0
arrow_downward

Ради аргумента мы можем переместить вычисление count в отдельную функцию, как показано ниже:

bool valid(int mid, int[][] matrix, int k) {
    int count = 0, m = matrix.length;
    for (int i = 0; i < m; i++) {
        int j = 0;
        while (j < m && matrix[i][j] <= mid) j++;
        count += j;
    }
    return (count < k);
}

Этот предикат будет делать то же самое, что и указанная вами операция. Здесь инвариант цикла заключается в том, что диапазон [lo, hi] всегда содержит kth наименьшее число двумерного массива.

Другими словами, lo <= solution <= hi

Теперь, когда цикл завершается, становится очевидным, что lo >= hi

Объединяя эти два свойства, мы получаем lo = solution = hi, поскольку solution является членом массива, можно сказать, что lo всегда находится в массиве после завершения цикла и будет правильно указывать на kth наименьший элемент.

person SALEH    schedule 17.03.2018
comment
Вот тут я в замешательстве. Почему solution всегда в массиве? Если мой диапазон равен [0,1,2,3,4,5,.....n-2,n-1,n] матрицы [[0,1],[n-1,n]], mid может быть любым числом из [0,n] между циклами. Однако, когда low›=hi и цикл завершается, почему low и mid должны быть между [0,1,n-1,n]. - person Snehasis Ghosh; 21.03.2018
comment
@ Snehasis Ghosh Переменная решения определяется как результат этой задачи. - person James LT; 24.09.2018

arrow_upward
0
arrow_downward

Потому что мы находим нижнюю границу с помощью двоичного поиска, и не может быть числа меньше числа (lo) в массиве, который может быть k-м наименьшим элементом.

person laxman sharma    schedule 21.01.2020