# 1182. Shortest Distance to Target Color 与目标颜色间的最短距离

@TOC

## # 题目描述

You are given an array colors, in which there are three colors: `1, 2 and 3`.

You are also given some queries. Each query consists of two integers `i` and `c`, return the shortest distance between the given index `i` and the target color `c`. If there is no solution return -1.

Example 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).
``````

Example 2:

``````Input: colors = [1,2], queries = [[0,3]]
Output: [-1]
Explanation: There is no 3 in the array.
``````

Constraints:

1. `1 <= colors.length <= 5*10^4`
2. `1 <= colors[i] <= 3`
3. `1 <= queries.length <= 5*10^4`
4. `queries[i].length == 2`
5. `0 <= queries[i][0] < colors.length`
6. `1 <= queries[i][1] <= 3`

## # 解题方法

### # 字典+二分查找

``````Input: colors = [1,1,2,1,3,2,2,3,3], queries = [[1,3],[2,2],[6,1]]

{
{1: 0, 1, 3},
{2: 2, 5, 6},
{3: 4, 7, 8}
}

``````

``````对于query = [5,3]，即找出离colors[5] = 2最近的3。在m[3]中做二分查找找出最接近5的数字，lower_bound()找到了7（说明最接近的值是4或者7，经过判断最终选择了4），所以距离是5 - 4 = 1；
``````

C++代码如下：

``````class Solution {
public:
vector<int> shortestDistanceColor(vector<int>& colors, vector<vector<int>>& queries) {
const int N = colors.size();
unordered_map<int, vector<int>> m;
for (int i = 0; i < N; ++i) {
m[colors[i]].push_back(i);
}
vector<int> res;
for (auto& query : queries) {
int cur = INT_MAX;
int target = query[0];
if (!m.count(query[1])) {
res.push_back(-1);
continue;
}
int pos = closest(m[query[1]], target);
res.push_back(abs(pos - target));
}
return res;
}
int closest(vector<int>& nums, int target) {
int pos = lower_bound(nums.begin(), nums.end(), target) - nums.begin();
if (pos == 0) return nums[0];
if (pos == nums.size()) return nums[nums.size() - 1];
if (nums[pos] - target < target - nums[pos - 1])
return nums[pos];
return nums[pos - 1];
}
};
``````

## # 日期

2019 年 9 月 23 日 —— 昨夜睡的早，错过了北京的烟火