ספירת מספרים שליליים במערך דו-ממדי

נתון מערך דו-ממדי mat המכיל מספרים שלמים המקיים את התנאים הבאים:

  • כל שורה במערך ממוינת בסדר עולה ממש (ללא מספרים זהים בשורה).
  • כל עמודה במערך ממוינת בסדר עולה ממש (ללא מספרים זהים בעמודה).

יש להחזיר מספר המספרים השליליים במערך mat.

לדוגמה, אם המערך mat מכיל את המספרים הבאים:

 0123456
0-99-72-64-55-28-10-5
1-53-46-46-38111322
2-63-48-27-12141623
3-44-29-100182028
40121420283035

אז יוחזר הערך 18, כי יש 18 מספרים שליליים במערך.

בהינתן שמספר השורות במערך הוא n ומספר העמודות במערך הוא m,

  • סיבוכיות הזמן הנדרשת לפתרון הבעיה היא לינארית O(n+m).
  • סיבוכיות המקום הנדרשת לפתרון הבעיה היא קבועה O(1).
דוגמה 1:
קלט:
mat =
[[-99, -72, -64, -55, -28, -10, -5],
 [-72, -53, -46, -38, 11, 13, 22],
 [-63, -48, -27, -12, 14, 16, 23],
 [-44, -29, -10, 0, 18, 20, 28],
 [0, 12, 14, 20, 28, 30, 35]]
פלט:
18

הסבר: ישנם 18 מספרים שליליים במערך.

דוגמה 2:
קלט:
mat =
[[-5, -4, -3],
 [-2, -1, 0],
 [1, 2, 3]]
פלט:
5

הסבר: ישנם 5 מספרים שליליים במערך.

דוגמה 3:
קלט:
mat =
[[0, 1, 2],
 [3, 4, 5],
 [6, 7, 8]]
פלט:
0

הסבר: אין מספרים שליליים במערך.

דוגמה 4:
קלט:
mat =
[[-10, -9, -8],
 [-7, -6, -5],
 [-4, -3, -2]]
פלט:
9

הסבר: כל המספרים במערך הם שליליים.

דוגמה 5:
קלט:
mat =
[[-1, 0, 1],
 [2, 3, 4],
 [5, 6, 7]]
פלט:
1

הסבר: יש רק מספר שלילי אחד במערך.

דוגמה 6:
קלט:
mat =
[[-3, -2, -1],
 [0, 1, 2],
 [3, 4, 5]]
פלט:
3

הסבר: ישנם 3 מספרים שליליים במערך.

דוגמה 7:
קלט:
mat =
[[-100],
 [-50],
 [0],
 [50],
 [100]]
פלט:
2

הסבר: ישנם 2 מספרים שליליים במערך.

דוגמה 8:
קלט:
mat =
[[-1, 2, 3],
 [-4, 5, 6],
 [-7, 8, 9]]
פלט:
3

הסבר: ישנם 3 מספרים שליליים במערך.

Loading...
נשמרLn 1, Col 1

קלט:

mat =
[[-99, -72, -64, -55, -28, -10, -5],
 [-72, -53, -46, -38, 11, 13, 22],
 [-63, -48, -27, -12, 14, 16, 23],
 [-44, -29, -10, 0, 18, 20, 28],
 [0, 12, 14, 20, 28, 30, 35]]

הפלט המבוקש:

18