Задача: 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 {
    function shortestDistanceColor($colors, $queries) {
        $queryResults = [];
        $hashmap = [];

        foreach ($colors as $i => $color) {
            if (!isset($hashmap[$color])) {
                $hashmap[$color] = [];
            }
            $hashmap[$color][] = $i;
        }

        foreach ($queries as $query) {
            list($target, $color) = $query;
            if (!isset($hashmap[$color])) {
                $queryResults[] = -1;
                continue;
            }

            $indexList = $hashmap[$color];
            $insert = $this->binarySearch($indexList, $target);

            if ($insert < 0) {
                $insert = -$insert - 1;
            }

            if ($insert == 0) {
                $queryResults[] = $indexList[$insert] - $target;
            } elseif ($insert == count($indexList)) {
                $queryResults[] = $target - $indexList[$insert - 1];
            } else {
                $leftNearest = $target - $indexList[$insert - 1];
                $rightNearest = $indexList[$insert] - $target;
                $queryResults[] = min($leftNearest, $rightNearest);
            }
        }
        return $queryResults;
    }

    private function binarySearch($arr, $target) {
        $left = 0;
        $right = count($arr) - 1;
        while ($left <= $right) {
            $mid = floor(($left + $right) / 2);
            if ($arr[$mid] == $target) {
                return $mid;
            } elseif ($arr[$mid] < $target) {
                $left = $mid + 1;
            } else {
                $right = $mid - 1;
            }
        }
        return -$left - 1;
    }
}

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