Задача: 1182. Shortest Distance to Target Color
Сложность: medium

Дан массив colors, содержащий три цвета: 1, 2 и 3.

Также даны несколько запросов. Каждый запрос состоит из двух целых чисел i и c. Верните наименьшее расстояние между заданным индексом i и целевым цветом c. Если решения нет, верните -1.

Пример:

Input: colors = [1,1,2,1,3,2,2,3,3], queries = [[1,3],[2,2],[6,1]]
Output: [3,0,3]
Explanation: 
The nearest 3 from index 1 is at index 4 (3 steps away).
The nearest 2 from index 2 is at index 2 itself (0 steps away).
The nearest 1 from index 6 is at index 3 (3 steps away).

👨‍💻 Алгоритм:

1⃣Инициализируйте хэш-таблицу для отображения каждого цвета в список индексов. Итерируйте по массиву colors и добавляйте каждый индекс в соответствующий список хэш-таблицы.

2⃣Для каждого запроса, содержащего i и c, если c не является одним из ключей в хэш-таблице, то colors не содержит c, поэтому верните -1. Иначе, найдите позицию i в соответствующем списке индексов indexList для поддержания упорядоченного порядка.

3⃣Если i меньше всех элементов в indexList, то i - indexList[0] является кратчайшим расстоянием. Если i больше всех элементов в indexList, то indexList[indexList.size() - 1] - i является кратчайшим расстоянием. Иначе, ближайшее появление c к i либо на индексе вставки, либо перед ним, поэтому рассчитайте расстояние от i до каждого из них и верните наименьшее.

😎 Решение

class Solution {
    func shortestDistanceColor(_ colors: [Int], _ queries: [[Int]]) -> [Int] {
        var queryResults = [Int]()
        var hashmap = [Int: [Int]]()

        for i in 0..<colors.count {
            hashmap[colors[i], default: [Int]()].append(i)
        }

        for query in queries {
            let target = query[0]
            let color = query[1]
            guard let indexList = hashmap[color] else {
                queryResults.append(-1)
                continue
            }

            let insert = indexList.binarySearch(target)

            if insert < 0 {
                let insertPos = -(insert + 1)
                if insertPos == 0 {
                    queryResults.append(indexList[insertPos] - target)
                } else if insertPos == indexList.count {
                    queryResults.append(target - indexList[insertPos - 1])
                } else {
                    let leftNearest = target - indexList[insertPos - 1]
                    let rightNearest = indexList[insertPos] - target
                    queryResults.append(min(leftNearest, rightNearest))
                }
            } else {
                queryResults.append(0)
            }
        }

        return queryResults
    }
}

extension Array where Element: Comparable {
    func binarySearch(_ value: Element) -> Int {
        var left = 0
        var right = self.count - 1

        while left <= right {
            let mid = (left + right) / 2
            if self[mid] == value {
                return mid
            } else if self[mid] < value {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
        return -(left + 1)
    }
}

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