Сбой тестового примера Leetcode
Я пытаюсь решить leetcode [проблема] [1]. Вопрос говорит о поиске в массиве 2d. Хотя мой код проходит большинство тестовых случаев, он терпит неудачу в конкретном тестовом примере.
/**
* @param {number[][]} matrix
* @param {number} target
* @return {boolean}
*/
/**
* @param {number[][]} matrix
* @param {number} target
* @return {boolean}
*/
var searchMatrix = function(matrix, target) {
let i = 0 ;
let j = matrix.length ;
while(i <= matrix.length - 1 && j >= 0){
if (matrix[i][j] == target){
return true
}
if (matrix[i][j] > target){
j--;
} else {
i++;
}
}
return false
};
searchMatrix([1,3],3)
Приведенное выше решение дает ложь, тогда как правильный ответ должен быть правдой. Что здесь не так? Немогу узнать! [1]: https://leetcode.com/problems/search-a-2d-matrix/
Как мне это сделать?
![Безумие обратных вызовов в javascript [JS]](https://i.imgur.com/WsjO6zJb.png)
Ответы 1
У этого вопроса есть два варианта: Leetcode и Geeks for Geeks.
Ваше вышеприведенное решение будет работать для платформы GFG, но не будет работать с leetcode.
Почему? Разница в обоих вопросах заключается в том, как расположены элементы. В вопросе leetcode первый элемент каждой строки будет больше, чем последний элемент предыдущей строки, чего нельзя сказать о GFG. В GFG у вас будет матрица, отсортированная по строкам и столбцам.
Ваше решение пройдет тестовые случаи GFG, но не сработает на leetcode. Следовательно, одно из оптимизированных решений, которое вы можете использовать, — это использовать его свойство вопроса и представить его как одномерный массив.
function searchMatrix(matrix, target){
let numberOfRows = matrix.length
let numberOFColums = matrix[0].length
let upperBoundOfMatrix = numberOfRows * numberOFColums - 1;
let start = 0
while(start <= upperBoundOfMatrix){
let mid = Math.floor(start + (upperBoundOfMatrix - start)/2);
let row = Math.floor(mid/numberOFColums);
let column = Math.floor(mid % numberOFColums);
if (matrix[row][column] == target){
return true
}
if (matrix[row][column] > target){
upperBoundOfMatrix = mid - 1;
} else {
start = mid + 1;
}
}
return false
}
ваша функция не учитывает, когда вход представляет собой одномерный массив, в этих случаях
matrix[i][j]всегда будет оцениваться какundefined, и поэтому вы никогда не вернете true.