ระยะทางที่สั้นที่สุดไปยังสีเป้าหมายใน 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] เนื่องจาก 3 ที่ใกล้ที่สุดจากดัชนี 1 อยู่ที่ดัชนี 4 (ห่างออกไป 3 ขั้น) จากนั้น 2 ที่ใกล้ที่สุดจากดัชนี 2 จะอยู่ที่ดัชนี 2 เอง (ห่างออกไป 0 ก้าว) และ 1 ที่ใกล้ที่สุดจากดัชนี 6 อยู่ที่ดัชนี 3 (ห่างออกไป 3 ก้าว)

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• สร้างเมทริกซ์หนึ่งตัวที่เรียกว่าดัชนีที่มี 4 แถว n :=จำนวนองค์ประกอบในอาร์เรย์สี

• สำหรับฉันอยู่ในช่วง 0 ถึง n – 1

  • แทรก i ลงใน index[colors[i]]

  • x :=การสืบค้น[i, 0] และ c :=การสืบค้น[i, 1]

  • ถ้าขนาดของ index[c] เป็น 0 ให้ใส่ -1 ลงใน ret และข้ามการวนซ้ำถัดไป

  • มัน :=องค์ประกอบแรกที่ไม่น้อยกว่า 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]|

  • แทรกขั้นต่ำของ 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;
   }
};
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]