Set Matrix Zeroes

Q: ما التعقيد الزمني لمسألة Set Matrix Zeroes؟

‏O(m·n) لمصفوفة m × n ، لأن كل خلية تُقرأ وتُكتب عددًا ثابتًا من المرات. لا يوجد حل أفضل، لأن أي خلية يتم تخطيها قد تكون 0 التي تغيّر الإجابة. المساحة الإضافية هي O(m + n) عند استخدام مصفوفتَي علامات، وO(1) عند استخدام الصف والعمود الأولين كعلامات.

متوسطالمصفوفات والسلاسل النصية التجزئة

+10

المدخلات عبارة عن شبكة m × n من الأعداد الصحيحة، مُعطاة صفًا تلو الآخر، لذا تقع matrix[i][j] في الصف i والعمود j. أينما احتوت الشبكة على 0، اجعل الصف بأكمله والعمود بأكمله أصفارًا. تُحتسب الأصفار الموجودة في البداية فقط: فالخلية التي تغيّرها إلى 0 لا تصفّر صفها أو عمودها. يمكنك تغيير الشبكة مباشرةً؛ أعدها.

الدالة

setZeroes(matrix: integer-2d-array) → integer-2d-array

matrixinteger-2d-array: شبكة من الأعداد الصحيحة، مع قائمة داخلية واحدة لكل صف
تُرجعinteger-2d-array: المصفوفة التي جُعل كل صف وكل عمود فيها يحتوي على 0 مساويًا لـ 0

القيود

m == matrix.length وn == matrix[i].length
1 ≤ m, n ≤ 1000 و m × n ≤ 5000
تحتوي جميع الصفوف m على n من القيم.
-1000 ≤ matrix[i][j] ≤ 1000

أمثلة

المدخلات: matrix = [[3, 8, 1], [5, 0, 7], [2, 6, 4]]
المخرجات: [[3, 0, 1], [0, 0, 0], [2, 0, 4]]
الشرح: يقع الصفر الوحيد في الصف 1، العمود 1. يصبح الصف 1 كله أصفارًا، وكذلك العمود 1، مما يحوّل 8 و6 إلى 0. لا تقع الزوايا الأربع على أيٍّ من الخطين، لذا تحتفظ بقيمها.

سؤال إضافي

يحتفظ النهج الأفضل أدناه بقيمتين منطقيتين إضافيتين. هل يمكنك الاكتفاء بواحدة، بحيث تمثل matrix[0][0] الصف الأول؟

الحل

الصفر الذي تكتبه يبدو تمامًا مثل الصفر الذي أُعطي لك، لذا فإن مسح الصفوف أثناء الفحص ينشر الأصفار في المصفوفة. افصل القراءة عن الكتابة: سجّل أولًا الصفوف والأعمدة التي احتوت على صفر، ثم امسحها. احتفظ بهذا السجل في مصفوفتين، أو في الصف الأول والعمود الأول من المصفوفة نفسها لتوفير مساحة إضافية O(1).

حدِّد الصفوف والأعمدة في مصفوفتين

الفكرة

تُصبح الخلية 0 بالضبط عندما كان صفها أو عمودها يحتوي على 0 في البداية. لذا سجّل قائمتين من المعلومات، zeroRow[i] وzeroCol[j]، في مرور لا يكتب أي شيء، ثم صفّر كل خلية يكون صفها أو عمودها معلّمًا. لن ينتشر التصفير، لأن جميع عمليات القراءة تتم قبل أول عملية كتابة.

يمرّ كل مرور على الخلايا m·n مرة واحدة، لذا يكون الزمن O(m·n)، وتحتوي المصفوفات على m + n قيمة منطقية.

الخوارزمية

أنشئ zeroRow مع m عناصر وzeroCol مع n عناصر، واجعلها جميعًا false.
افحص كل خلية. عندما تكون matrix[i][j] تساوي 0، عيّن zeroRow[i] وzeroCol[j] إلى true.
افحص كل خلية مرة أخرى وعيّنها إلى 0 عندما تكون zeroRow[i] أو zeroCol[j] تساوي true.
أعِد المصفوفة.

def setZeroes(matrix):
    m, n = len(matrix), len(matrix[0])
    zero_row = [False] * m
    zero_col = [False] * n
    # Pass 1: only read, so a new zero can never spread further.
    for i in range(m):
        for j in range(n):
            if matrix[i][j] == 0:
                zero_row[i] = True
                zero_col[j] = True
    # Pass 2: write.
    for i in range(m):
        for j in range(n):
            if zero_row[i] or zero_col[j]:
                matrix[i][j] = 0
    return matrix

استخدم الصف والعمود الأولين كعلامتين

الفكرة

يحتوي العمود الأول على خلية واحدة لكل صف، ويحتوي الصف الأول على خلية واحدة لكل عمود، وهذان هما شكلَا مصفوفتَي العلامات. لذا فإن كتابة 0 في الصف i والعمود j تكتب 0 في matrix[i][0] وmatrix[0][j]. وهذا لا يفقد أي معلومات: فكل واحدة من هاتين الخليتين تقع في خط يجب أن يصبح 0 على أي حال.

الصف 0 والعمود 0 بيانات وعلامات في آنٍ واحد، ووضع علامة فيهما يخفي ما إذا كانا يحتويان على 0 خاص بهما. لذا تحقّق منهما أولًا واحتفظ بالإجابتين في متغيرين منطقيين. ضع العلامات واملأ الخلايا التي تحقق i ≥ 1 وj ≥ 1 فقط، وامسح الصف 0 والعمود 0 أخيرًا، لأن عملية الملء تقرؤهما.

في المثال الثاني، يبقى العدد 3 في الصف 1 والعمود 1، لأن علامتيه، matrix[1][0] = 9 وmatrix[0][1] = 4، ليستا 0. يظل الزمن O(m·n)، مع استخدام متغيرين منطقيين كذاكرة إضافية (O(m·n) في R، التي تنسخ المُدخل أولًا).

الخوارزمية

اضبط firstRowZero إذا كان الصف 0 يحتوي على 0، وfirstColZero إذا كان العمود 0 يحتوي على 0.
لكل خلية تحتوي على 0، حيث i ≥ 1 وj ≥ 1، اضبط matrix[i][0] وmatrix[0][j] على 0.
لكل خلية حيث i ≥ 1 وj ≥ 1، اضبطها على 0 عندما تكون matrix[i][0] أو matrix[0][j] تساوي 0.
إذا كان firstRowZero صحيحًا، فاضبط الصف 0 على 0. وإذا كان firstColZero صحيحًا، فاضبط العمود 0 على 0.
أعِد المصفوفة.

def setZeroes(matrix):
    m, n = len(matrix), len(matrix[0])
    # The first row and column will hold the markers, so remember first
    # whether they need to become zero themselves.
    first_row_zero = any(matrix[0][j] == 0 for j in range(n))
    first_col_zero = any(matrix[i][0] == 0 for i in range(m))
    # Mark: a zero inside the matrix flags its row in column 0
    # and its column in row 0.
    for i in range(1, m):
        for j in range(1, n):
            if matrix[i][j] == 0:
                matrix[i][0] = 0
                matrix[0][j] = 0
    # Fill the inside from the markers.
    for i in range(1, m):
        for j in range(1, n):
            if matrix[i][0] == 0 or matrix[0][j] == 0:
                matrix[i][j] = 0
    # The marker row and column go last.
    if first_row_zero:
        for j in range(n):
            matrix[0][j] = 0
    if first_col_zero:
        for i in range(m):
            matrix[i][0] = 0
    return matrix

أخطاء شائعة وحالات حدّية

مسح صف وعمود بمجرد العثور على 0. في المثال الأول، يؤدي 0 الجديد في الصف 1، العمود 2 إلى مسح العمود 2، ولا يبقى سوى 3 في أعلى اليسار.
السماح لـ matrix[0][0] بتحديد كل من الصف 0 والعمود 0. في [[1, 2, 3], [0, 5, 6], [7, 8, 9]]، يتسبب 0 في العمود 0 عندئذٍ في مسح الصف 0 عن طريق الخطأ.
مسح الصف 0 أو العمود 0 قبل التعبئة. في [[0, 2, 3], [4, 5, 6], [7, 8, 9]]، يبدو عندئذٍ أن كل عمود محدد، وتصبح المصفوفة بأكملها 0.
نسيان الصفوف المفردة. عند وجود صف واحد، لا تفعل الحلقات التي تبدأ من 1 شيئًا، وتتولى القيم المنطقية المهمة كلها: يجب أن تصبح [[1, 0, 3]] [[0, 0, 0]].

أسئلة شائعة3

لماذا لا يمكنك تعيين الأصفار أثناء فحص المصفوفة؟

يبدو الرقم 0 الذي تكتبه مثل الرقم 0 الأصلي. عندما يصل إليه المسح، يمسح صفه وعموده، ثم تنتشر الأصفار الجديدة أكثر. سجّل كل صفر أصلي قبل تغيير أي خلية.

ما التعقيد الزمني لمسألة Set Matrix Zeroes؟

‏O(m·n) لمصفوفة m × n، لأن كل خلية تُقرأ وتُكتب عددًا ثابتًا من المرات. لا يوجد حل أفضل، لأن أي خلية يتم تخطيها قد تكون 0 التي تغيّر الإجابة. المساحة الإضافية هي O(m + n) عند استخدام مصفوفتَي علامات، وO(1) عند استخدام الصف والعمود الأولين كعلامات.

هل يمكنك تحديد الخلايا بقيمة خاصة بدلًا من 0؟

تكتب بعض الحلول قيمةً نائبة في الخلايا المطلوب مسحها، ثم تحوّل القيم النائبة إلى أصفار في النهاية. لا ينجح ذلك إلا إذا كان من المستحيل ظهور القيمة النائبة في الإدخال، وهو أمر نادرًا ما تضمنه مصفوفة من الأعداد الصحيحة. كما أن كتابتها على امتداد صف وعمود لكل 0 يستغرق وقتًا قدره O(m·n·(m + n)).

def setZeroes(matrix):
    # اكتب الشيفرة هنا

اختبار #1

اختبار #2

وسيط

matrix = [[3, 8, 1], [5, 0, 7], [2, 6, 4]]

الإخراج المتوقع

[[3, 0, 1], [0, 0, 0], [2, 0, 4]]