सी++ में लक्ष्य रंग के लिए सबसे छोटी दूरी

मान लीजिए कि हमारे पास एक सरणी रंग है, जिसमें तीन रंग हैं: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 की सीमा में

  • मुझे इंडेक्स में डालें [रंग [i]]

  • एक्स:=प्रश्न [i, 0] और सी:=प्रश्न [i, 1]

  • अगर इंडेक्स का आकार [सी] 0 है, तो -1 को रिट में डालें, और अगले पुनरावृत्ति को छोड़ दें

  • it :=पहला तत्व जो x से कम नहीं है – अनुक्रमणिका का पहला तत्व [c]

  • op1:=अनंत, op2:=अनंत

  • अगर यह =सूचकांक का आकार [सी], इसे 1 op1 से घटाएं:=|x - अनुक्रमणिका [सी, यह]|

  • अन्यथा जब यह =0, तब op1 :=|x - index[c, it]|

  • अन्यथा op1 :=|x - index[c, it]|, इसे 1 से घटाएं और op2 :=|x - index[c, it]|

  • रिट में कम से कम 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]