文章目錄
-
- 1. 題目
- 2. 解題
-
- 2.1 二分查找
- 2.2 DP
1. 題目
給你一個數組 colors，裡面有 1、2、 3 三種顔色。
我們需要在 colors 上進行一些查詢操作 queries，其中每個待查項都由兩個整數 i 和 c 組成。
現在請你幫忙設計一個算法，查找從索引 i 到具有目标顔色 c 的元素之間的最短距離。
如果不存在解決方案，請傳回 -1。
示例 1：
輸入：colors = [1,1,2,1,3,2,2,3,3],
queries = [[1,3],[2,2],[6,1]]
輸出：[3,0,3]
解釋：
距離索引 1 最近的顔色 3 位于索引 4（距離為 3）。
距離索引 2 最近的顔色 2 就是它自己（距離為 0）。
距離索引 6 最近的顔色 1 位于索引 3（距離為 3）。
示例 2：
輸入：colors = [1,2], queries = [[0,3]]
輸出：[-1]
解釋：colors 中沒有顔色 3。
提示：
1 <= colors.length <= 5*10^4
1 <= colors[i] <= 3
1 <= queries.length <= 5*10^4
queries[i].length == 2
0 <= queries[i][0] < colors.length
1 <= queries[i][1] <= 3 複制
來源：力扣（LeetCode）
連結：https://leetcode-cn.com/problems/shortest-distance-to-target-color
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。
2. 解題
- 找到下标 i 左右最近的 c 顔色花
2.1 二分查找
class Solution {
public:
vector<int> shortestDistanceColor(vector<int>& colors, vector<vector<int>>& queries) {
unordered_map<int,set<int>> m;
for(int i = 0; i < colors.size(); ++i)
{
m[colors[i]].insert(i);
}
vector<int> ans(queries.size(), -1);
int l, r, dis, i = 0;
for(auto& q : queries)
{
if(colors[q[0]] == q[1])
{
ans[i++] = 0;
continue;
}
auto next = m[q[1]].lower_bound(q[0]);//二分查找
r = next==m[q[1]].end() ? INT_MAX : *next-q[0];
l = INT_MAX;
if(next != m[q[1]].begin())
{
l = q[0] - *(--next);
}
dis = min(l, r);
ans[i++] = dis==INT_MAX ? -1 : dis;
}
return ans;
}
}; 複制
972 ms 114.4 MB
2.2 DP
- 記住左右兩側的最近花的位置，正反掃描2次
class Solution {
public:
vector<int> shortestDistanceColor(vector<int>& colors, vector<vector<int>>& queries) {
int i, j, n = colors.size(), dis, idx, c;
vector<int> pos(4,-1);
vector<vector<int>> left(n, vector<int>(4, INT_MAX));
vector<vector<int>> right(n, vector<int>(4, INT_MAX));
for(i = 0; i < n; ++i)
{
pos[colors[i]] = i;
left[i][1] = pos[1]==-1 ? INT_MAX : i-pos[1];
left[i][2] = pos[2]==-1 ? INT_MAX : i-pos[2];
left[i][3] = pos[3]==-1 ? INT_MAX : i-pos[3];
}
pos[1] = pos[2] = pos[3] = -1;
for(i = n-1; i >= 0; --i)
{
pos[colors[i]] = i;
right[i][1] = pos[1]==-1 ? INT_MAX : pos[1]-i;
right[i][2] = pos[2]==-1 ? INT_MAX : pos[2]-i;
right[i][3] = pos[3]==-1 ? INT_MAX : pos[3]-i;
}
vector<int> ans(queries.size(), -1);
for(i = 0; i < queries.size(); ++i)
{
idx = queries[i][0];
c = queries[i][1];
dis = min(left[idx][c], right[idx][c]);
ans[i] = dis==INT_MAX ? -1 : dis;
}
return ans;
}
}; 複制
888 ms 131.7 MB