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 :=রঙের অ্যারেতে উপাদানের সংখ্যা

• আমি 0 থেকে n – 1

  পরিসরে

  • index[colors[i]]

    -এ i ঢোকান

  • x :=প্রশ্ন[i, 0] এবং c :=প্রশ্ন[i, 1]

  • যদি সূচকের আকার [c] 0 হয়, তাহলে ret এ -1 ঢোকান এবং পরবর্তী পুনরাবৃত্তি এড়িয়ে যান

  • এটি :=প্রথম উপাদান যা x এর কম নয় - সূচকের প্রথম উপাদান[c]

  • op1 :=অসীম, op2 :=অসীম

  • যদি এটি =সূচকের আকার[c], তাহলে এটিকে 1 op1 কমিয়ে দিন :=|x – index[c, it]|

  • অন্যথায় যখন এটি =0, তারপর op1 :=|x – index[c, it]|

  • অন্যথায় op1 :=|x – index[c, it]|, 1 দ্বারা কমিয়ে op2 :=|x – index[c, it]|

  • ret

    -এ ন্যূনতম op1 এবং op2 সন্নিবেশ করান

• রিটার্ন রিটার্ন

উদাহরণ (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]