1352. Product of the Last K Numbers

On a campus represented as a 2D grid, there are N workers and M bikes, with N <= M. Each worker and bike is a 2D coordinate on this grid.

Our goal is to assign a bike to each worker. Among the available bikes and workers, we choose the (worker, bike) pair with the shortest Manhattan distance between each other, and assign the bike to that worker. (If there are multiple (worker, bike) pairs with the same shortest Manhattan distance, we choose the pair with the smallest worker index; if there are multiple ways to do that, we choose the pair with the smallest bike index). We repeat this process until there are no available workers.

The Manhattan distance between two points p1 and p2 is Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|.

Return a vector ans of length N, where ans[i] is the index (0-indexed) of the bike that the i-th worker is assigned to.

Example 1:

Input: workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]]
Output: [1,0]
Explanation:
Worker 1 grabs Bike 0 as they are closest (without ties), and Worker 0 is assigned Bike 1. So the output is [1, 0].

Example 2:

Input: workers = [[0,0],[1,1],[2,0]], bikes = [[1,0],[2,2],[2,1]]
Output: [0,2,1]
Explanation:
Worker 0 grabs Bike 0 at first. Worker 1 and Worker 2 share the same distance to Bike 2, thus Worker 1 is assigned to Bike 2, and Worker 2 will take Bike 1. So the output is [0,2,1].

Note:

1. 0 <= workers[i][j], bikes[i][j] < 1000
2. All worker and bike locations are distinct.
3. 1 <= workers.length <= bikes.length <= 1000

这道题用一个二维数组来表示一个校园坐标，上面有一些人和共享单车，人的数量不多余单车的数量，现在要让每一个人都分配一辆单车，人和单车的距离是用曼哈顿距离表示的。这里的分配方法其实是有一些 confuse 的，并不是每个人要拿离其距离最近的单车，也不是每辆单车要分配给距离其最近的人，而是要从所有的 单车-人 对儿中先挑出距离最短的一对儿，然后再挑出距离第二短的组合，以此类推，直到所有的人都被分配到单车了为止。这样的话就需要求出每一对人车距离，将所有的人车距离，和对应的人和车的标号都存到一个二维数组中。然后对这个二维数组进行排序，这里需要重写排序规则，将人车距离小的排前面，假如距离相等，则将人标号小的放前面，假如人的标号也相同，则就将车标号小的放前面。对人车距离数组排好序之后，此时需要两个数组来分别标记每个人被分配的车标号，和每个车的主人标号。现在从最小的人车距离开始取，若此时的人和车都没有分配，则进行分配，遍历完所有的人车距离之后，最终的结果就存在了标记每个人分配的车标号的数组中，参见代码如下：

解法一：

class Solution {
public:
    vector<int> assignBikes(vector<vector<int>>& workers, vector<vector<int>>& bikes) {
        int m = workers.size(), n = bikes.size();
        vector<int> assignedWorker(m, -1), assignedBike(n, -1);
        vector<vector<int>> dist;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                int d = abs(workers[i][0] - bikes[j][0]) + abs(workers[i][1] - bikes[j][1]);
                dist.push_back({d, i, j});
            }
        }
        sort(dist.begin(), dist.end(), [](vector<int>& a, vector<int>& b) {
                return a[0] < b[0] || (a[0] == b[0] && a[1] < b[1]) || (a[0] == b[0] && a[1] == b[1] && a[2] < b[2]);
            });
        for (auto &a : dist) {
            if (assignedWorker[a[1]] == -1 && assignedBike[a[2]] == -1) {
                assignedWorker[a[1]] = a[2];
                assignedBike[a[2]] = a[1];
            }
        }
        return assignedWorker;
    }
};

上面的解法虽然可以通过 OJ，但是并不是很高效，应该是排序的部分拖慢了速度。其实这道题的范围是有限的，因为车和人的坐标是有限的，最大的人车距离也不会超过 2000，那么利用桶排序来做就是个不错的选择，只需要 2001 个桶就行了，桶中放的是 pair 对儿，其中　buckets[i] 表示距离是i的人和车的标号组成的 pair 对儿。这样当计算出每个人车距离后，将其放入对应的桶中即可，就自动排好了序。然后开始遍历每个桶，由于每个桶中可能不止放了一个 pair 对儿，所以需要遍历每个桶中所有的组合，然后的操作就和上面的相同了，若此时的人和车都没有分配，则进行分配，遍历完所有的人车距离之后，最终的结果就存在了标记每个人分配的车标号的数组中，参见代码如下：

解法二：

class Solution {
public:
    vector<int> assignBikes(vector<vector<int>>& workers, vector<vector<int>>& bikes) {
        int m = workers.size(), n = bikes.size();
        vector<int> assignedWorker(m, -1), assignedBike(n, -1);
        vector<vector<pair<int, int>>> buckets(2001);
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                int dist = abs(workers[i][0] - bikes[j][0]) + abs(workers[i][1] - bikes[j][1]);
                buckets[dist].push_back({i, j});
            }
        }
        for (int dist = 0; dist <= 2000; ++dist) {
            for (int k = 0; k < buckets[dist].size(); ++k) {
                if (assignedWorker[buckets[dist][k].first] == -1 && assignedBike[buckets[dist][k].second] == -1) {
                    assignedWorker[buckets[dist][k].first] = buckets[dist][k].second;
                    assignedBike[buckets[dist][k].second] = buckets[dist][k].first;
                }
            }
        }
        return assignedWorker;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1057

类似题目：

Campus Bikes II

参考资料：

https://leetcode.com/problems/campus-bikes/

https://leetcode.com/problems/campus-bikes/discuss/305603/Java-Fully-Explained

https://leetcode.com/problems/campus-bikes/discuss/376283/Easy-C%2B%2B-solution-with-comments

https://leetcode.com/problems/campus-bikes/discuss/308738/C%2B%2B-bucket-sort-O(M*N)-time-and-space-solution

LeetCode All in One 题目讲解汇总(持续更新中…)

---

转载请注明来源于 Grandyang 的博客 (grandyang.com)，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 grandyang@qq.com