在C ++中到目标颜色的最短距离
假设我们有一个数组颜色,其中有三种颜色:1、2和3。我们给出了一些查询。每个查询由两个整数i和c组成,我们必须找到给定索引i与目标颜色c之间的最短距离。如果没有解决方案,则返回-1。因此,如果颜色数组类似于[1,1,2,1,3,2,2,3,3],而查询数组类似于[[1,3],[2,2],[6,1]],输出将为[3,0,3]。这是因为距索引1最近的3位于索引4(距离3步)。然后,距离索引2最近的2就是索引2本身(0步)。与索引6最接近的1在索引3(距离3步)。
为了解决这个问题,我们将遵循以下步骤-
创建一个有4行的索引矩阵,n:=颜色数组中的元素数
对于I范围从0到n–1
将我插入index[colors[i]]
x:=查询[i,0]和c:=查询[i,1]
如果index[c]的大小为0,则将-1插入ret,并跳过下一个迭代
它:=第一个不小于x的元素–index[c]的第一个元素
op1:=无穷大,op2:=无穷大
如果它=index[c]的大小,则将其减少1op1:=|x–index[c,it]|
否则,当它=0时,则op1:=|x–index[c,it]|
否则,op1:=|x–index[c,it]|减1,然后op2:=|x–index[c,it]|
将op1和op2的最小值插入ret
返回ret
范例(C++)
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h> using namespace std; void print_vector(vector<auto> v){ cout << "["; for(int i = 0; i<v.size(); i++){ cout << v[i] << ", "; } cout << "]"<<endl; } class Solution { public: vector<int> shortestDistanceColor(vector<int>& colors, vector<vector<int>>& queries) { vector < vector <int> >idx(4); int n = colors.size(); for(int i = 0; i < n; i++){ idx[colors[i]].push_back(i); } vector <int> ret; for(int i = 0; i < queries.size(); i++){ int x = queries[i][0]; int c = queries[i][1]; if(idx[c].size() == 0){ ret.push_back(-1); continue; } int it = lower_bound(idx[c].begin(), idx[c].end() , x) - idx[c].begin(); int op1 = INT_MAX; int op2 = INT_MAX; if(it == idx[c].size()){ it--; op1 = abs(x - idx[c][it]); } else if(it == 0){ op1 = abs(x - idx[c][it]); } else{ op1 = abs(x - idx[c][it]); it--; op2 = abs(x - idx[c][it]); } ret.push_back(min(op1, op2)); } return ret; } }; main(){ vector<int> v = {1,1,2,1,3,2,2,3,3}; vector<vector<int>> v1 = {{1,3},{2,2},{6,1}}; Solution ob; print_vector(ob.shortestDistanceColor(v, v1)); }
输入值
[1,1,2,1,3,2,2,3,3] [[1,3],[2,2],[6,1]]
输出结果
[3,0,3]