C++でのターゲットカラーまでの最短距離

配列の色があり、1、2、3の3色があるとします。いくつかのクエリを実行しました。各クエリは2つの整数iとcで構成されており、指定されたインデックスiとターゲットカラーcの間の最短距離を見つける必要があります。解決策がない場合は、-1を返します。したがって、colors配列が[1,1,2,1,3,2,2,3,3]のようであり、querys配列が[[1,3]、[2,2]、[6,1]のようである場合]]、出力は[3,0,3]になります。これは、インデックス1から最も近い3がインデックス4（3ステップ離れている）にあるためです。次に、インデックス2から最も近い2は、インデックス2自体にあります（0ステップ離れています）。そして、インデックス6から最も近い1は、インデックス3にあります（3ステップ離れています）。

これを解決するには、次の手順に従います-

• 4行のインデックスと呼ばれる1つの行列を作成します。n：=カラー配列の要素数

• 0からn–1の範囲のIの場合

  • iをindex[colors[i]]

    に挿入します

  • x：=クエリ[i、0]およびc：=クエリ[i、1]

  • index [c]のサイズが0の場合、retに-1を挿入し、次の反復をスキップします

  • it：=x以上の最初の要素– index [c]

    の最初の要素

  • op1：=無限大、op2：=無限大

  • =index [c]のサイズの場合、1つ減らしますop1：=| x – index [c、it] |

  • それ以外の場合、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]