在C ++中到目标颜色的最短距离

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个数组颜色，其中有三种颜色：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]的大小，则将其减少1 op1：= | 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]

以上是 在C ++中到目标颜色的最短距离 的全部内容， 来源链接： utcz.com/z/335161.html

回到顶部