Рубрики
Без рубрики

Решение: самые слабые ряды в матрице (вер. 1)

Это является частью серии объяснений решений LeetCode (индекс). Если вам понравилось это решение или fou … с меткой алгоритмы, JavaScript, Java, Python.

LeetCode Solutions (161 серия деталей)

Это является частью серии объяснений решения LeetCode ( index ). Если вам понравилось это решение или нашли его полезным, Пожалуйста, нравится Этот пост и/или upvote Мое решение по сообщению на форумах LeetCode Анкет

Примечание : Это моя первая версия решения решения для этой проблемы. Я предпочитаю это решение, но моя вторая версия технически имеет лучшую сложность времени ( O (m * log (n + k)) против. O (m * n) ), а также лучшая сложность пространства ( Ok) против. O (м) ), но это делает это с помощью Функция бинарного поиска , a Max-HEAP Структура данных , а также Бит манипуляции , которые являются довольно сложными инструментами для «легкой» проблемы.

Если вы хотите проверить более сложное решение, Вы можете найти полный разрыв здесь .

Проблема LeetCode #1337 (легко): самые слабые ряды в матрице

Описание:

Данный а M * n матрица мат из тех (представляющих солдат) и нули (представляющие гражданских лиц), возвращают индексы k Самые слабые ряды в матрице, упорядоченные от самых слабых до самых сильных.

Строка i слабее ряда j , если количество солдат в ряд i меньше, чем количество солдат в ряду j , или у них такое же количество солдат, но i меньше чем j . Солдаты всегда стоят на границе ряда, то есть всегда могут появиться сначала, а затем нули.

Примеры:

Вход: mat = [[1,1,0,0,0],[1,1,1,1,0],[1,0,0,0,0],[1,1,0,0,0],[1,1,1,1,1]]
Выход: [2,0,3]
Объяснение: Количество солдат для каждой строки: ряд 0 -> 2 строка 1 -> 4 строка 2 -> 1 строка 3 -> 2 строки 4 -> 5 рядов, заказанных от самых слабых до самых сильных, -[2,0,3, 1,4]
Вход: mat = [[1,0,0,0],[1,1,1,1],[1,0,0,0],[1,0,0,0]]
Выход: [0,2]
Объяснение: Количество солдат для каждой строки: ряд 0 -> 1 строка 1 -> 4 строки 2 -> 1 строка 3 -> 1 строки, заказанные от самых слабых до самых сильных, -[0,2,3,1]

Ограничения:

  • M.Length
  • n [i] .length
  • 2, м
  • 1
  • Mat [i] [j] это либо 0 или 1 Анкет

Идея:

Поскольку солдаты всегда находятся в передней части каждого ряда, мы можем заметить, что первый ряд, показывающий гражданина в любом данном столбце, является первым индексом, который должен быть представлен в нашем массиве ответов ( ans ).

Это означает, что мы можем найти правильные элементы Анс По порядку, просто итерация через столбцы, сверху вниз и подтолкнуть ряды к Ответ один, как их граждане подвергаются воздействию. Затем нам просто нужно отследить, какие ряды уже закончили с флагом в нашем посещенном массиве ( vis ).

Как только мы заполнили Анс С самым слабым K Индексы строк, мы должны вернуть ANS Анкет

Реализация:

Для JavaScript мы должны использовать легкий типичный Uint8array для VIS Анкет

Для Java и C ++ мы должны объявить наш массив ANS с фиксированным измерением, а затем использовать отдельную переменную индекса ( kix ), чтобы разместить элементы в соответствующие положения.

Код JavaScript:

var kWeakestRows = function(M, K) {
    let y = M.length, x = M[0].length,
        vis = new Uint8Array(y), ans = []
    for (let j = 0; j <= x; j++)
        for (let i = 0; i < y; i++) {
            if (!vis[i] && !M[i][j]) ans.push(i), vis[i]++
            if (ans.length === K) return ans
        }
};

Код Python:

class Solution:
    def kWeakestRows(self, M: List[List[int]], K: int) -> List[int]:
        y, x = len(M), len(M[0])
        vis, ans = [0] * y, []
        for j in range(x+1):
            for i in range(y):
                if not vis[i] and (j == x or not M[i][j]):
                    ans.append(i)
                    vis[i] = 1
                if len(ans) == K: return ans

Код Java:

class Solution {
    public int[] kWeakestRows(int[][] M, int K) {
        int y = M.length, x = M[0].length, kix = 0;
        int[] vis = new int[y], ans = new int[K];
        for (int j = 0; j <= x; j++)
            for (int i = 0; i < y; i++) {
                if (vis[i] == 0 && (j == x || M[i][j] == 0)) {
                    ans[kix++] = i;
                    vis[i]++;
                }
                if (kix == K) return ans;
            }
        return ans;
    }
}

C ++ Код:

class Solution {
public:
    vector kWeakestRows(vector>& M, int K) {
        int y = M.size(), x = M[0].size(), kix = 0;
        vector vis(y), ans(K);
        for (int j = 0; j <= x; j++)
            for (int i = 0; i < y; i++) {
                if (!vis[i] && (j == x || !M[i][j])) {
                    ans[kix++] = i;
                    vis[i]++;
                }
                if (kix == K) return ans;
            }
        return ans;
    }
};

LeetCode Solutions (161 серия деталей)

Оригинал: “https://dev.to/seanpgallivan/solution-the-k-weakest-rows-in-a-matrix-2679”

Читайте ещё по теме: