Golang | LeetCode

Задача: 378. Kth Smallest Element in a Sorted Matrix
Сложность: medium

Дана матрица размером n x n, где каждая строка и каждый столбец отсортированы в порядке возрастания. Верните k-й наименьший элемент в матрице.

Заметьте, что это k-й наименьший элемент в отсортированном порядке, а не k-й уникальный элемент.

Вы должны найти решение с использованием памяти лучше, чем O(n²).

Пример:

Input: matrix = [[-5]], k = 1
Output: -5

👨‍💻

Алгоритм:

1⃣Инициализировать мин-кучу H. В нашем решении мы будем рассматривать каждую строку как отдельный список. Поскольку столбцы также отсортированы, мы можем рассматривать каждый столбец как отдельный список.

2⃣Взять первые элементы из min(N, K) строк, где N представляет количество строк, и добавить каждый из этих элементов в кучу. Важно знать, к какой строке и столбцу принадлежит элемент, чтобы в дальнейшем перемещаться по соответствующему списку.

3⃣Мин-куча будет содержать тройки информации (значение, строка, столбец). Куча будет упорядочена по значениям, и мы будем использовать номера строк и столбцов для добавления следующего элемента, если текущий элемент будет удален из кучи.

😎

Решение:

package main

import (
    "strings"
)

type Solution struct{}

func (s Solution) dfs(word string, length int, visited []bool, dictionary map[string]bool) bool {
    if length == len(word) {
        return true
    }
    if visited[length] {
        return false
    }
    visited[length] = true
    for i := len(word) - 1; i > length; i-- {
        if dictionary[word[length:i]] && s.dfs(word, i, visited, dictionary) {
            return true
        }
    }
    return false
}

func (s Solution) findAllConcatenatedWordsInADict(words []string) []string {
    dictionary := make(map[string]bool)
    for _, word := range words {
        dictionary[word] = true
    }
    var answer []string
    for _, word := range words {
        visited := make([]bool, len(word))
        if s.dfs(word, 0, visited, dictionary) {
            answer = append(answer, word)
        }
    }
    return answer
}

func main() {
    solution := Solution{}
    words := []string{"cat", "cats", "catsdogcats", "dog", "dogcatsdog", "hippopotamuses", "rat", "ratcatdogcat"}
    result := solution.findAllConcatenatedWordsInADict(words)
    for _, word := range result {
        println(word)
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Please open Telegram to view this post