LintCode 280: Closest City

280. Closest City

There are many cities on a two-dimensional plane, all cities have their own names c[i]c[i], and location coordinates (x[i],y[i])(x[i],y[i]) (both are integers). There are qq group queries, and each group query gives a city name. You need to answer the city name that is the closest to the city and has the same xx or yy.

Example

Example 1：

Input: x = [3, 2, 1] y = [3, 2, 3] c = ["c1", "c2", "c3"] q = ["c1", "c2", "c3"]

Output: ["c3", "NONE", "c1"]

Explanation: For c1, c3 is the same as its y, the closest distance is (3-1)+(3-3)=2

For c2, no city is the same as its x or y

For c3, c1 is the same as his y, the closest distance is (3-1)+(3-3)=2

Notice

If there are multiple answers that satisfy the conditions, the one with the smallest lexicographic name is output.

The distance here is the Euler distance: the absolute value of the coordinate difference of xx plus the absolute value of the coordinate difference of yy.

0 ≤ Number of cities ≤ 10^5, 

0 ≤ Ask for the number of groups ≤ 10, 

1 ≤ Coordinate range 10^9

​​ 解法1：

这题被标识为简单，但我觉得其实做出来挺花时间。

我的解法是把每个X和Y坐标都建一个vector数组，装在这个X或Y坐标上的城市列表。然后排序。对于query数组，找到这个城市在对应X和Y坐标上的位置，然后前后找对应的邻近城市，然后比较大小。

注意：

1) for (auto & elem : x_cities) 和 for (auto & elem : y_cities) 要加引用，因为内部x_cities和y_cities排序，产生了变化。

2) 当比较大小是相等时，用字典排序。

这个解法时间复杂度是O(nlogn)，效率不高。

class Solution {
public:
    /**
     * @param x: an array of integers, the x coordinates of each city[i]
     * @param y: an array of integers, the y coordinates of each city[i]
     * @param c: an array of strings that represent the names of each city[i]
     * @param q: an array of strings that represent the names of query locations
     * @return: the closest city for each query
     */
    vector<string> NearestNeighbor(vector<int> &x, vector<int> &y, vector<string> &c, vector<string> &q) {
        int n = x.size();
        vector<string> result;
        unordered_map<int, vector<pair<int, string>>> x_cities;  //x->list of (y, city)
        unordered_map<int, vector<pair<int, string>>> y_cities;  //y->list of (x, city)
        
        unordered_map<string, int> city_x; //city->x
        unordered_map<string, int> city_y; //city->y
        
        for (int i = 0; i < n; ++i) {
            x_cities[x[i]].push_back({y[i], c[i]});
            city_x[c[i]] = x[i];
        }
        
        for (int i = 0; i < n; ++i) {
            y_cities[y[i]].push_back({x[i], c[i]});
            city_y[c[i]] = y[i];
        }
        
        for (auto &elem : x_cities) { //注意加引用
            sort(elem.second.begin(), elem.second.end()); //sort y values under the same x
        }

        for (auto &elem : y_cities) { //注意加引用
            sort(elem.second.begin(), elem.second.end()); //sort x values under the same y
        }

        for (int i = 0; i < q.size(); ++i) {
           int min_dist = INT_MAX;
            string closest_city = "NONE";
            int target_x = city_x[q[i]];
            int target_y = city_y[q[i]];
            int dist = 0;
            if (x_cities[target_x].size() > 1) {
                int find_y_index = binary_search(x_cities[target_x], target_y);
                if (find_y_index != -1) { //one city does not need to search
                    if (find_y_index > 0) {
                        dist = x_cities[target_x][find_y_index].first - x_cities[target_x][find_y_index - 1].first;
                        if (min_dist > dist || (min_dist == dist && x_cities[target_x][find_y_index - 1].second < closest_city)) {
                            min_dist = dist;
                            closest_city = x_cities[target_x][find_y_index - 1].second;
                        }
                    }
                    if (find_y_index < x_cities[target_x].size() - 1) {
                        dist = x_cities[target_x][find_y_index + 1].first - x_cities[target_x][find_y_index].first;
                        if (min_dist > dist || (min_dist == dist && x_cities[target_x][find_y_index + 1].second < closest_city)) {
                            min_dist = dist;
                            closest_city = x_cities[target_x][find_y_index + 1].second;
                        }
                    }
                }
            }
            
            if (y_cities[target_y].size() > 1) { //one city does not need to search
                int find_x_index = binary_search(y_cities[target_y], target_x);
                if (find_x_index != -1) {    
                    if (find_x_index > 0) {
                        dist = y_cities[target_y][find_x_index].first - y_cities[target_y][find_x_index - 1].first;
                        if (min_dist > dist || (min_dist == dist && y_cities[target_y][find_x_index - 1].second < closest_city)) {
                            min_dist = dist;
                            closest_city = y_cities[target_y][find_x_index - 1].second;
                        }
                    }
                    if (find_x_index < y_cities[target_y].size() - 1) {
                        dist = y_cities[target_y][find_x_index + 1].first - y_cities[target_y][find_x_index].first;
                        if (min_dist > dist || min_dist == dist && y_cities[target_y][find_x_index + 1].second < closest_city) {
                            min_dist = dist;
                            closest_city = y_cities[target_y][find_x_index + 1].second;
                        }
                    }
                }
            }
            result.push_back(closest_city);
        }
        
        return result;
    }
    
private:
    int binary_search(vector<pair<int, string>> arr, int target) {
        int start = 0, end = arr.size() - 1;
        
        while(start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (arr[mid].first < target) {
                start = mid;
            } else if (arr[mid].first > target) {
                end = mid;
            } else {
                return mid;
            }
        }
        
        if (arr[end].first == target) return end;
        if (arr[start].first == target) return start;
        return -1;
    }
};
           

解法2：直接硬比。时间复杂度O(mn)。

class Solution {
public:
    /**
     * @param x: an array of integers, the x coordinates of each city[i]
     * @param y: an array of integers, the y coordinates of each city[i]
     * @param c: an array of strings that represent the names of each city[i]
     * @param q: an array of strings that represent the names of query locations
     * @return: the closest city for each query
     */
    vector<string> NearestNeighbor(vector<int> &x, vector<int> &y, vector<string> &c, vector<string> &q) {
        int cx, cy;
        vector <string> near;
        for(int queryIndex = 0; queryIndex < q.size(); queryIndex++)
        {
            string city = "NONE";
            int minDistance = 0;
            int findIndex = 0;             
            for(int i = 0; i < c.size(); i++)
            {
                if(c[i] == q[queryIndex])
                {
                    cx = x[i];
                    cy = y[i];
                    findIndex = i;
                    break;
                }
            }
            
            for(int i = 0; i < c.size(); i++)
            {
                if(i == findIndex)
                {
                    continue;
                }
                
                if(x[i] == cx)
                {
                    if(abs(cy - y[i]) < minDistance || minDistance == 0)
                    {
                        minDistance = abs(cy - y[i]);
                        city = c[i];
                    }
                    if(abs(cy - y[i]) == minDistance && c[i] < city)
                    {
                        minDistance = abs(cy - y[i]);
                        city = c[i];
                    }
                }
                
                if(y[i] == cy)
                {
                    if(abs(cx - x[i]) < minDistance || minDistance == 0)
                    {
                        minDistance = abs(cx - x[i]);
                        city = c[i];
                    }
                    
                    if(abs(cx - x[i]) == minDistance && c[i] < city)
                    {
                        minDistance = abs(cx - x[i]);
                        city = c[i];
                    }
                }
             }
            
            near.push_back(city);
        
        }
        return near;
    }
};