ধরুন আমাদের একটি color অ্যারে আছে যেখানে তিনটি রঙ: 1, 2 এবং 3। কিছু কুয়েরি দেওয়া আছে। প্রতিটি কুয়েরি দুটি ইন্টিজার i এবং c সম্বহ করে, আমাদের দেওয়া ইনডেক্স i এবং টার্গেট কালার c-এর মধ্যবর্তী ন্যূনতম দূরত্ব খুঁজে বের করতে হবে। যদি সমাধান না থাকে, তবে -1 রিটার্ন করুন। যেন colors অ্যারে [1,1,2,1,3,2,2,3,3], এবং queries অ্যারে [[1,3], [2,2], [6,1]], তবে আউটপুট হবে [3,0,3]। কারণ ইনডেক্স 1 থেকে নিকটতম 3 ইনডেক্স 4-এ (৩ স্টেপ দূরত্বে)। তারপর ইনডেক্স 2 থেকে নিকটতম 2 ইনডেক্স 2-এই (০ স্টেপ দূরত্বে)। এবং ইনডেক্স 6 থেকে নিকটতম 1 ইনডেক্স ৩-এ (৩ স্টেপ দূরত্বে)।
সমাধান পদ্ধতি
- 4 সারির একটি ম্যাট্রিক্স index বানান, n := color অ্যারেতে উপাদান সংখ্যা
- i = 0 থেকে n-1 পর্যন্ত লুপ চালান
- i-কে index[colors[i]]-এ ইনসার্ট করুন
- x := queries[i, 0] এবং c := queries[i, 1]
- যদি index[c]-র আকার 0 হয়, তবে ret-এ -1 ইনসার্ট করুন এবং পরবর্তী ইটারেশনে যান
- it := x-এর চেয়ে কম না হয় এমন প্রথম উপাদান - index[c]-র প্রথম উপাদান
- op1 := infinity, op2 := infinity
- যদি it = index[c]-র আকার, তবে it ১ কমানো, op1 := |x - index[c, it]|
- অন্যথায় যখন it = 0, তবে op1 := |x - index[c, it]|
- অন্যথায় op1 := |x - index[c, it]|, it ১ কমানো এবং 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; } }; 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]
