Search a 2D Matrix
لديك شبكة من الأعداد الصحيحة matrix تضم m صفوف وn أعمدة، وعدد صحيح target. كل صف مرتب ترتيبًا تصاعديًا، والقيمة الأولى في كل صف أكبر من القيمة الأخيرة في الصف الذي يسبقه. أعد true إذا ظهرت target في الشبكة، وfalse خلاف ذلك، في زمن O(log(m × n)).
الدالة
- matrixinteger-2d-array
- الشبكة، المعطاة كقائمة من الصفوف، مرتبة صفًا تلو الآخر
- targetinteger
- القيمة التي يجب البحث عنها
- تُرجعboolean
- صحيح إذا كان الهدف ضمن الشبكة، وخاطئ فيما عدا ذلك
القيود
1 ≤ m, n ≤ 100، حيثm = matrix.lengthوn = matrix[i].length- لكل صف الطول نفسه
n. -104 ≤ matrix[i][j], target ≤ 104- كل صف مرتب ترتيبًا تصاعديًا صارمًا، وتكون القيمة الأولى في كل صف أكبر من القيمة الأخيرة في الصف السابق.
أمثلة
- المدخلات
- matrix = [[2, 5, 9, 14], [17, 21, 26, 30], [33, 38, 45, 52]]target = 26
- المخرجات
- true
- الشرح
- عند القراءة صفًا تلو الآخر، تشكّل القيم الـ12 قائمة مرتبة واحدة. يبحث البحث الثنائي في المواضع من 0 إلى 11، فيتحقق من 21 في الموضع 5 (أصغر من المطلوب)، ثم من 33 في الموضع 8 (أكبر من المطلوب)، ثم يعثر على 26 في الموضع 6.
- المدخلات
- matrix = [[2, 5, 9, 14], [17, 21, 26, 30], [33, 38, 45, 52]]target = 16
- المخرجات
- false
- الشرح
- سيأتي 16 بعد 14، وهي آخر قيمة في الصف 0، وقبل 17، وهي أول قيمة في الصف 1. لا يوجد شيء بينهما، لذا فإن 16 ليست في الشبكة.
سؤال إضافي
افترض أن الصفوف قد تكون بأطوال مختلفة، مع بقائها مرتبة من البداية إلى النهاية. كيف ستحوّل موضعًا إلى صف وعمود، وما تكلفة البحث؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
اقرأ المصفوفة صفًا صفًا، من اليسار إلى اليمين، كما لو كانت قائمة طويلة واحدة. ماذا تلاحظ بشأن ترتيب القيم في تلك القائمة؟
تعني القاعدتان معًا أن المصفوفة بأكملها، عند قراءتها صفًا تلو الآخر، هي قائمة واحدة مرتبة من
m × nقيمة. يمكنك إجراء بحث ثنائي فيها من دون إنشائها مطلقًا.ابحث ثنائيًا ضمن المواضع من
0إلىm × n - 1. يقع الموضعpفي الصفp / nوالعمودp % n(القسمة الصحيحة)، لذا تقرأ كل خطوة خلية واحدة وتستبعد نصف المواضع المتبقية.
الحل
تجعل قاعدتا الترتيب معًا الشبكة، عند قراءتها صفًا صفًا، قائمةً واحدة مرتبة من القيم m × n. ابحث بحثًا ثنائيًا في تلك القائمة حسب الموضع، ثم حوّل كل موضع إلى صف وعمود باستخدام عملية قسمة واحدة. عندئذٍ تحتاج شبكة من 100 × 100 إلى 14 مقارنة كحد أقصى بدلًا من 10000.
تحقّق من كل خلية
الفكرة
قارن كل خلية مع target وأعِد true عند التطابق، وfalse بعد فحص الخلية الأخيرة. يفحص كل خلية، لذا فهو صحيح لأي شبكة، سواء أكانت مرتبة أم لا. لا يستفيد أبدًا من الترتيب، لذا تتطلب شبكة بحجم 100 في 100 ما يصل إلى 10000 مقارنة.
الخوارزمية
- لكل صف في
matrix، افحص كل قيمة بالترتيب. - إذا كانت القيمة تساوي
target، فأعِدtrue. - بعد الحلقات، أعِد
false.
def searchMatrix(matrix, target):
for row in matrix:
for value in row:
if value == target:
return True
return Falseامشِ من الزاوية العلوية اليمنى
الفكرة
انطلاقًا من الخلية العلوية اليمنى، تكون كل قيمة إلى اليسار أصغر، وكل قيمة إلى الأسفل أكبر. إذا كانت قيمة الخلية أكبر من target، فإن العمود الذي تحتها يكون أكبر أيضًا: تحرّك خطوة إلى اليسار واستبعد ذلك العمود. وإذا كانت أصغر، فإن الصف الذي إلى يسارها يكون أصغر أيضًا: تحرّك خطوة إلى الأسفل واستبعد ذلك الصف.
في المثال الأول، 14 أصغر من 26، لذا تحرّك خطوة إلى الأسفل نحو 30. قيمة 30 أكبر، لذا تحرّك خطوة إلى اليسار نحو 26، فتجد المطابقة. كل خطوة تستبعد صفًا أو عمودًا، لذا لن تحتاج إلى أكثر من m + n خطوات: 200 لشبكة أبعادها 100 في 100. لا يتطلب هذا المسح سوى أن تكون الصفوف والأعمدة مرتبة، لذا فهو لا يستفيد من نصف ما توفره لك هذه الشبكة.
الخوارزمية
- ابدأ من الصف
0والعمود الأخير. - ما دام الصف والعمود داخل الشبكة، اقرأ الخلية.
- إذا كانت تساوي
target، فأعِدtrue. - إذا كانت أكبر، فتحرّك عمودًا واحدًا إلى اليسار؛ وإذا كانت أصغر، فتحرّك صفًا واحدًا إلى الأسفل.
- عندما تخرج من الشبكة، أعِد
false.
def searchMatrix(matrix, target):
# Start at the top-right corner: left is smaller, down is larger.
r, c = 0, len(matrix[0]) - 1
while r < len(matrix) and c >= 0:
value = matrix[r][c]
if value == target:
return True
if value > target:
c -= 1 # every value below in this column is larger still
else:
r += 1 # every value to the left in this row is smaller still
return Falseالبحث الثنائي في الشبكة المسطّحة
الفكرة
رقّم الخلايا صفًا تلو الآخر: يحتوي الصف 0 على المواضع من 0 إلى n - 1، ويحتوي الصف 1 على n إلى 2n - 1، وهكذا. كل صف مرتب ويبدأ بعد الموضع الذي انتهى عنده الصف السابق، لذا تزداد القيم كلما تقدمنا في المواضع. هذه قائمة مرتبة، لذا ينطبق عليها البحث الثنائي.
لا تنشئ القائمة أبدًا. يقع الموضع p في الصف p / n والعمود p % n، باستخدام القسمة الصحيحة. في المثال الأول n = 4، لذا يقع الموضع 6 في الصف 1، والعمود 2، الذي يحتوي على 26. كل مقارنة تقلّص إلى النصف المواضع التي قد تحتوي على target: بحد أقصى 14 مقارنةً لـ 10000 خلية، مع استخدام مؤشرين إضافيين من الذاكرة.
الخوارزمية
- ليكن
mوnعددَي الصفوف والأعمدة، واضبطlo = 0وhi = m × n - 1. - ما دام
lo ≤ hi، خذmidفي منتصف المسافة بينهما. - اقرأ
value = matrix[mid / n][mid % n]. - إذا كانت
valueتساويtarget، فأعِدtrue. وإذا كانت أصغر، فاضبطlo = mid + 1؛ وإلا فاضبطhi = mid - 1. - عند انتهاء الحلقة، أعِد
false.
def searchMatrix(matrix, target):
rows, cols = len(matrix), len(matrix[0])
# Read row by row, the cells form one sorted list of rows * cols values.
# Position p of that list is matrix[p // cols][p % cols].
lo, hi = 0, rows * cols - 1
while lo <= hi:
mid = (lo + hi) // 2
value = matrix[mid // cols][mid % cols]
if value == target:
return True
if value < target:
lo = mid + 1
else:
hi = mid - 1
return False
أخطاء شائعة وحالات حدّية
- القسمة على عدد الصفوف بدلًا من الأعمدة. الموضع
pيقع في الصفp / n؛ وعند استخدامmبدلًا منه، تنجح الشيفرة على الشبكات المربعة وتفشل في شبكة من 3 صفوف و4 أعمدة. - في نسخة البحثين، عدم التعامل مع
targetإذا كانت قيمته أقل منmatrix[0][0]. لا يبدأ أي صف عند هذه القيمة أو بعدها، ويصل فهرس الصف-1إلى البحث الثاني. - استخدام الحلقة بشرط
lo < hiمع اعتبارhiحدًا شاملًا. شبكة 1 في 1 تحتوي علىtargetتُرجعfalse، لأن الحلقة لا تُنفَّذ أبدًا. - في Lua وR، نسيان التحويل إلى الفهارس التي تبدأ من 1: الموضع
pهو الصفp / n + 1، والعمودp % n + 1.
أسئلة شائعة3
ما هو التعقيد الزمني للبحث في مصفوفة ثنائية الأبعاد؟
يعمل البحث الثنائي على الشبكة المسطّحة في زمن O(log(m × n)) ومساحة O(1): 14 مقارنة كحد أقصى لـ 10000 خلية. بما أن log(m × n) = log m + log n، فهو يعادل البحث عن الصف ثم البحث داخله.
هل ينبغي لك استخدام أسلوب السير إلى الزاوية العلوية اليمنى أم البحث الثنائي؟
تستغرق المسيرة على طول الزوايا O(m + n) خطوة، ولا تتطلب سوى ترتيب الصفوف والأعمدة، لذا فهي تحل أيضًا الحالة التي قد يبدأ فيها صف أسفل نهاية الصف الذي يعلوه. أما عندما يبدأ كل صف فوق النقطة التي ينتهي عندها الصف السابق، كما في هذه الحالة، فيكون البحث الثنائي أسرع.
هل يُعدّ إجراء بحثين ثنائيين، أحدهما للصف والآخر داخله، صحيحًا أيضًا؟
نعم. ابحث بالبحث الثنائي في العمود الأول عن الصف الأخير الذي تكون قيمته الأولى أقل من target أو مساوية له، ثم ابحث ثنائيًا في ذلك الصف. يستغرق ذلك O(log m + log n)، وهو الحد نفسه. ينفّذ البحث الواحد العمل نفسه بحلقة واحدة وحالات حدّية أقل.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def searchMatrix(matrix, target):
# اكتب الكود هنااختبار #1
اختبار #2
الوسائط
matrix = [[2, 5, 9, 14], [17, 21, 26, 30], [33, 38, 45, 52]] target = 26
الإخراج المتوقع
true