Khoảng Cách Ngắn Nhất Đến Màu Mục Tiêu Trong C++

Giả sử chúng ta có mảng colors chứa ba màu: 1, 2, 3. Cho một số truy vấn, mỗi truy vấn gồm hai số nguyên i và c, tìm khoảng cách ngắn nhất giữa chỉ số i và màu mục tiêu c. Nếu không có giải pháp, trả về -1. Ví dụ, colors = [1,1,2,1,3,2,2,3,3], queries = [[1,3], [2,2], [6,1]], đầu ra = [3,0,3]. Giải thích: màu 3 gần nhất từ chỉ số 1 ở chỉ số 4 (3 bước), màu 2 từ chỉ số 2 ở chính chỉ số 2 (0 bước), màu 1 từ chỉ số 6 ở chỉ số 3 (3 bước).

Để giải quyết, chúng ta làm theo các bước:

• Tạo ma trận index 4 hàng, n := số phần tử trong colors.

• Với i từ 0 đến n-1: chèn i vào index[colors[i]].

• Với mỗi truy vấn: x = queries[i][0], c = queries[i][1].

• Nếu index[c] rỗng, thêm -1 vào kết quả.

• Tìm it = lower_bound(index[c], x).

• Tính op1, op2 là khoảng cách đến phần tử tại it và it-1 (nếu có).

• Thêm min(op1, op2) vào kết quả.

Ví dụ (C++)

Hãy xem 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;
    }
};

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

Đầu vào

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

Đầu ra

[3,0,3]