मान लीजिए हमारे पास एक कलर ऐरे है जिसमें तीन कलर्स हैं: 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 पंक्तियों वाला एक मैट्रिक्स idx बनाएं, n := कलर ऐरे में एलिमेंट्स की संख्या
i को 0 से n-1 तक लूप करें:
i को idx[colors[i]] में इंसर्ट करें
x := queries[i][0] और c := queries[i][1]
अगर idx[c] का साइज 0 है, तो ret में -1 इंसर्ट करें, और अगले इटरेशन पर जाएं
it := पहला एलिमेंट जो x से कम नहीं है - idx[c] का पहला एलिमेंट
op1 := इनफिनिटी, op2 := इनफिनिटी
अगर it = idx[c] का साइज, तो it को 1 घटाएं, op1 := |x - idx[c][it]|
अन्यथा जब it = 0, तो op1 := |x - idx[c][it]|
अन्यथा op1 := |x - idx[c][it]|, it को 1 घटाएं और op2 := |x - idx[c][it]|
ret में op1 और op2 का मिनिमम इंसर्ट करें
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;
}
};
int 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]