Khoảng cách ngắn nhất đến màu mục tiêu trong C ++

Giả sử chúng ta có một màu mảng, trong đó có ba màu:1, 2 và 3. Chúng ta đã đưa ra một số truy vấn. Mỗi truy vấn bao gồm hai số nguyên i và c, chúng ta phải tìm khoảng cách ngắn nhất giữa chỉ số i đã cho và màu mục tiêu c. Nếu không có giải pháp nào, thì trả về -1. Vì vậy, nếu mảng màu giống như [1,1,2,1,3,2,2,3,3] và mảng truy vấn giống như [[1,3], [2,2], [6,1 ]], đầu ra sẽ là [3,0,3]. Điều này là do chỉ số 3 gần nhất từ ​​chỉ số 1 nằm ở chỉ số 4 (cách 3 bước). Sau đó số 2 gần nhất từ ​​chỉ số 2 là chính chỉ số 2 (cách 0 bước). Và chỉ số 1 gần nhất từ ​​chỉ số 6 nằm ở chỉ số 3 (cách 3 bước).

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Tạo một ma trận được gọi là chỉ mục với 4 hàng, n:=số phần tử trong mảng màu

• cho tôi trong phạm vi từ 0 đến n - 1

  • chèn i vào chỉ mục [color [i]]

  • x:=queries [i, 0] và c:=queries [i, 1]

  • nếu kích thước của chỉ mục [c] là 0, thì hãy chèn -1 vào ret và bỏ qua lần lặp tiếp theo

  • it:=phần tử đầu tiên không nhỏ hơn x - phần tử đầu tiên của chỉ mục [c]

  • op1:=infinity, op2:=infinity

  • if it =size of index [c], hãy giảm nó đi 1 op1:=| x - index [c, it] |

  • ngược lại khi nó =0 thì op1:=| x - index [c, it] |

  • ngược lại op1:=| x - index [c, it] |, giảm nó đi 1 và op2:=| x - index [c, it] |

  • chèn tối thiểu op1 và op2 vào ret

• trả lại ret

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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));
}

Đầu vào

[1,1,2,1,3,2,2,3,3]
[[1,3],[2,2],[6,1]]

Đầu ra

[3,0,3]