Swift | Вопросы собесов

🤔 Как бы реализовал словарь в Swift при помощи массива?

В Swift словарь (Dictionary) представляет собой структуру данных, которая хранит пары ключ-значение и обеспечивает быстрый доступ к значениям по ключу (O(1) в среднем). Но если бы мы хотели реализовать словарь на основе массива, то пришлось бы использовать линейный поиск, что делает операции менее эффективными (O(n)).

🚩

Реализация словаря через массив кортежей

Один из простых способов создать словарь на базе массива — использовать массив кортежей (ключ, значение).

struct ArrayDictionary<Key: Equatable, Value> {
    private var items: [(Key, Value)] = []  // Храним пары ключ-значение

    // Получение значения по ключу
    func value(for key: Key) -> Value? {
        for (k, v) in items {
            if k == key {
                return v
            }
        }
        return nil
    }

    // Добавление или обновление значения
    mutating func insert(value: Value, for key: Key) {
        for i in 0..<items.count {
            if items[i].0 == key {
                items[i].1 = value  // Обновляем значение, если ключ уже есть
                return
            }
        }
        items.append((key, value))  // Добавляем новую пару
    }

    // Удаление элемента по ключу
    mutating func remove(for key: Key) {
        items.removeAll { $0.0 == key }
    }
}

// Пример использования
var myDict = ArrayDictionary<String, Int>()
myDict.insert(value: 42, for: "age")
myDict.insert(value: 30, for: "height")

print(myDict.value(for: "age")!)  // 42
myDict.remove(for: "age")
print(myDict.value(for: "age"))   // nil

🚩

Оптимизация: Использование бинарного поиска

Если мы отсортируем массив по ключам, можно использовать бинарный поиск (O(log n)) для ускорения поиска ключа.

struct SortedArrayDictionary<Key: Comparable, Value> {
    private var items: [(Key, Value)] = []

    // Бинарный поиск индекса ключа
    private func index(of key: Key) -> Int? {
        var left = 0
        var right = items.count - 1
        while left <= right {
            let mid = (left + right) / 2
            if items[mid].0 == key {
                return mid
            } else if items[mid].0 < key {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
        return nil
    }

    // Получение значения по ключу
    func value(for key: Key) -> Value? {
        if let index = index(of: key) {
            return items[index].1
        }
        return nil
    }

    // Вставка с сохранением сортировки
    mutating func insert(value: Value, for key: Key) {
        if let index = index(of: key) {
            items[index].1 = value
        } else {
            items.append((key, value))
            items.sort { $0.0 < $1.0 }  // Сортируем после вставки
        }
    }
}

// Использование
var sortedDict = SortedArrayDictionary<String, Int>()
sortedDict.insert(value: 50, for: "b")
sortedDict.insert(value: 20, for: "a")
sortedDict.insert(value: 70, for: "c")

print(sortedDict.value(for: "b")!)  // 50

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

Please open Telegram to view this post