Самый эффективный способ решения проблемы, связанной с 2D матрицей в python

Question

1. Мне дали двумерную матрицу (порядок n * m), изначально все элементы установлены в ноль

2. далее, учитывая несколько пар, например (строка, столбец).

3. Мне нужно добавить 1 к каждому элементу данной строки и каждому элементу данного col для каждой пары

4. В конце концов янужно считать нет. нечетных элементов в 2D матрице

Order:- N~no. of rows 
        M~no. of cols
        N*M <= 10^6
        Q~no. of pairs given <=10^5

Я разработал Sol. из этого

    import numpy as np
    n, m, q = map(int, input().split())
    arr = np.zeros((n, m))  
    for _ in range(q):  #This loop works for each pair one by one 
        x ,y = (map(int, input().split()))    #(row,col) given considering matrix indexing start from 1
        x -= 1  
        y -= 1

        if x <= n and y <= m:
            arr[x, :] += 1                       # +1 to each element of that row
            arr[:, y] += 1                       # +1 to each element of that col

    print(len(arr[arr % 2 != 0]))             #printing the no. of odd elements in the end

это прекрасно работало, когда n, m, q < 300

, но для 2-го случая я получаю ошибку ограничения времени

проблема здесь как N.M = 10^6 и Q = 10^5

есть ли другой эффективный способ, которым я могу это реализовать !!

Answer 1

Я думаю, что для существенного ускорения процесса вам нужно работать с массивом 1d.

Предположим, мы распределяем массив 2d в C-style order (row-major). m и n - количество строк и столбцов матрицы соответственно, x и y - индексы выбранной строки и столбца соответственно.

arr = np.zeros(m * n)

# to add 1 to rows
arr[x * n: (x + 1) * n] += 1

# to add 1 to columns 
mask = np.arange(m) + y
arr[mask] += 1

В конце дня количество нечетных элементов может быть подсчитано как

len(np.where(mask % 2 != 0))

Answer 2

Вы можете сделать это без создания двумерной матрицы, например:

N = int(input())
M = int(input())

row_count = [0] * (N + 1)
col_count = [0] * (M + 1)

q = int(input())

for _ in range(q):
    row, col = map(int, input().split())

    row_count[row] += 1
    col_count[col] += 1

odd_rows_count = 0
for row in row_count:
    if row % 2:
        odd_rows_count += 1

odd_cols_count = 0
for col in col_count:
    if col % 2:
        odd_cols_count += 1

print(
    odd_rows_count * (M - odd_cols_count)    # Odd = odd + even
    + (N - odd_rows_count) * odd_cols_count  # Odd = even + odd
)

Ввод:

3
4
3
1 1
1 2
1 1

Вывод:

5

---

ВремяСложность: O(n + m + q)

Пространство Сложность: O(n + m)