Решение: поиск 2D Matrix II

Решения LeetCode (161 часть серии)

Это является частью серии объяснений решения LeetCode ( index ). Если вам понравилось это решение или нашел его полезным, Пожалуйста, как этот пост и/или УПОТАТЬ Мое решение пост на форумах LeetCode Отказ

Проблема летета № 240 (средний): поиск 2D Matrix II

Описание:

( Перейти к : Идея решения Код : JavaScript | Python |. Java |. C ++

Напишите эффективный алгоритм, который ищет цель Значение в м х н Целое число Матрица Отказ Матрица Имеет следующие свойства:

• Целые числа в каждой строке сортируются в восходящем слева направо.
• Целые числа в каждом столбце отсортированы в восходящемся части сверху вниз.

Примеры:

Ограничения:

• m.length
• n [I] .length
• 1, М.
• -10 ^ 9 [I] [J] ^ 9
• Все целые числа в каждой строке отсортированы в порядке возрастания.
• Все целые числа в каждом столбце отсортированы в порядке возрастания.
• -10^9^9

Идея:

( Перейти к : Описание проблемы Код : JavaScript | Python |. Java |. C ++

Наивный подход здесь будет проверять каждую ячейку на Сложность времени O (m * n) Отказ Очевидное улучшение на это будет использовать бинарный поиск Но поскольку матрица ( m ) сортируется как по ряду, так и по столбцу, мы можем действительно думать о каждом клетка ( m [i] [j] ) как средняя точка в более длинной «строке», включая все клетки влево, а также ниже текущей ячейки.

Если мы начнем с верхнего правого угла М и обрабатывать это как модифицированный бинарный поиск, мы можем устранить целую строку или целый столбец каждый раз, когда мы проверяем клетка :

Затем нам просто нужно настроить наши Я или J Значение Чтобы перейти к верхней правой углу «средней точке» оставшейся матрицы каждый раз, чтобы сузить в нашей цели ( T ):

Это бросит временной сложность для O (m + n) Отказ

( Примечание: это работает так же, как и начиная с левого нижнего угла. )

Реализация:

Для всех, кроме Java, мы можем использовать побитовые не Оператор ( ~ ) проверить на граничное состояние J Потому что это вернет ложное значение ( 0 ) только когда J это -1 .

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

Код JavaScript:

( Перейти к : Описание проблемы Идея решения

var searchMatrix = function(M, T) {
    let y = M.length, i = 0, j = M[0].length - 1
    while (i < y && ~j) {
        let cell = M[i][j]
        if (cell === T) return true
        else if (cell > T) j--
        else i++
    }
    return false
};

Код Python:

( Перейти к : Описание проблемы Идея решения

class Solution:
    def searchMatrix(self, M: List[List[int]], T: int) -> bool:
        y, i, j = len(M), 0, len(M[0]) - 1
        while i < y and ~j:
            cell = M[i][j]
            if cell == T: return True
            elif cell > T: j -= 1
            else: i += 1
        return False

Java код:

( Перейти к : Описание проблемы Идея решения

class Solution {
    public boolean searchMatrix(int[][] M, int T) {
        int y = M.length, i = 0, j = M[0].length - 1;
        while (i < y && j >= 0) {
            int cell = M[i][j];
            if (cell == T) return true;
            else if (cell > T) j--;
            else i++;
        }
        return false;
    }
}

C ++ код:

( Перейти к : Описание проблемы Идея решения

class Solution {
public:
    bool searchMatrix(vector>& M, int T) {
        int y = M.size(), i = 0, j = M[0].size() - 1;
        while (i < y && ~j) {
            int cell = M[i][j];
            if (cell == T) return true;
            else if (cell > T) j--;
            else i++;
        }
        return false;
    }
};

Решения LeetCode (161 часть серии)

Оригинал: “https://dev.to/seanpgallivan/solution-search-a-2d-matrix-ii-4lc”