תיאור השאלה
You are given an m x n integer matrix where each row is sorted in non-decreasing order, and the first integer of each row is greater than the last integer of the previous row. Given an integer target, return true if it is in the matrix and false otherwise, in O(log(m * n)) time.
איך פותרים?
המטריצה היא בעצם מערך ממוין אחד באורך m·n. עושים חיפוש בינארי על האינדקסים, ומתרגמים כל אינדקס לשורה (חלוקה ב־n) ולעמודה (שארית). סיבוכיות: O(log(m·n)).
פתרון קוד
JavaScript
Python
function searchMatrix(matrix, target) {
const m = matrix.length;
const n = matrix[0].length;
let left = 0;
let right = m * n - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
const value = matrix[Math.floor(mid / n)][mid % n];
if (value === target) return true;
if (value < target) left = mid + 1;
else right = mid - 1;
}
return false;
}
לעבור את ראיון העבודה הבא שלך בהצלחה
קורס דיגיטלי מקיף עם +25 שיעורים מעשיים, כשעתיים של וידאו, וליווי של מראיין בכיר.