2019 力扣杯 校园自行车分配——Java版

2. 校园自行车分配

在由 2D 网格表示的校园里有 n 位工人（worker）和 m 辆自行车（bike），n <= m。所有工人和自行车的位置都用网格上的 2D 坐标表示。

我们需要为每位工人分配一辆自行车。在所有可用的自行车和工人中，我们选取彼此之间曼哈顿距离最短的工人自行车对 (worker, bike) ，并将其中的自行车分配給工人。如果有多个 (worker, bike) 对之间的曼哈顿距离相同，那么我们选择工人索引最小的那对。类似地，如果有多种不同的分配方法，则选择自行车索引最小的一对。不断重复这一过程，直到所有工人都分配到自行车为止。

给定两点 p1 和 p2 之间的曼哈顿距离为 Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|。

返回长度为 n 的向量 ans，其中 a[i] 是第 i 位工人分配到的自行车的索引（从 0 开始）。

示例 1：

输入：workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]]
输出：[1,0]
解释：
工人 1 分配到自行车 0，因为他们最接近且不存在冲突，工人 0 分配到自行车 1 。所以输出是 [1,0]。

示例 2：

输入：workers = [[0,0],[1,1],[2,0]], bikes = [[1,0],[2,2],[2,1]]
输出：[0,2,1]
解释：
工人 0 首先分配到自行车 0 。工人 1 和工人 2 与自行车 2 距离相同，因此工人 1 分配到自行车 2，工人 2 将分配到自行车 1 。因此输出为 [0,2,1]。

提示：

1. 0 <= workers[i][j], bikes[i][j] < 1000
2. 所有工人和自行车的位置都不相同。
3. 1 <= workers.length <= bikes.length <= 1000

分析：这个题我们首先得到所有的(工人索引，自行车索引，曼哈顿距离)作为存储对象，然后以曼哈顿距离为主，工人索引次之，自行车索引方式再次之的方式将这些对象按升序排列，最后按顺序遍历三元组给工人分配自行车即可。

实现代码如下：

class Solution {
    public int[] assignBikes(int[][] workers, int[][] bikes) {
		int n = workers.length, m = bikes.length;
		int[] ans = new int[n];
		boolean[] visw = new boolean[n];
		boolean[] visb = new boolean[m];
		Node[] list = new Node[n * m];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				Node node = new Node(i, j,
						Math.abs(workers[i][0] - bikes[j][0]) + Math.abs(workers[i][1] - bikes[j][1]));
				list[i * m + j] = node;
			}
		}
		Comparator<Node> cmp = new MyComparator();
		Arrays.sort(list, cmp);
		int cnt = 0;
		for (int i = 0; i < n * m; i++) {
			if (!visw[list[i].id_worker] && !visb[list[i].id_bike]) {
				ans[list[i].id_worker] = list[i].id_bike;
				visw[list[i].id_worker] = true;
				visb[list[i].id_bike] = true;
				cnt++;
			}
			if (cnt == n)
				break;
		}
		/*
		 * for (int i : ans) { System.out.println(i); }
		 */
		return ans;
	}

	static class Node {
		int id_worker;
		int id_bike;
		int dis;

		public Node(int id_worker, int id_bike, int dis) {
			this.id_worker = id_worker;
			this.id_bike = id_bike;
			this.dis = dis;
		}
	}

	static class MyComparator implements Comparator<Node> {
		@Override
		public int compare(Node a, Node b) {
			if (a.dis == b.dis) {
				if (a.id_worker == b.id_worker)
					return a.id_bike < b.id_bike ? -1 : 1;
				else
					return a.id_worker < b.id_worker ? -1 : 1;
			} else
				return a.dis < b.dis ? -1 : 1;
		}
	}
}

这里我们自己创建了一个类Node，这个类的作用是存储某个工到某个自行车的距离，事先记录下来，用作评判依据，还使用了Arrays.sort()；将存储了包含全部工人到全部自行车的的距离的Node对象排序，但是排序，Arrays.sort()的排序规则并不能满足题目中所给的规则，显然Java的开发者也考虑到这个情况，我们可以继承Comparator接口，实现compare方法，自定义排序规则，按照题目所给的规则进行排序。为什么a.id_bike < b.id_bike 时，返回-1，这是因为在Java的源码中
for (int j=i; j>low && c.compare(dest[j-1], dest[j])>0; j–)
swap(dest, j, j-1);
如果c.compare(dest[j-1], dest[j])>0，就进行交换，如果为负数，说明不用交换，满足规则。

这里程序是通过了，但是在写代码的过程中我将Node类和MyComparator类作为外部类或者内部类都是超时状态，但是将之改为静态内部类就OK了，我也很纳闷原因？我找到一篇博客，但是我不知道是不是这个原因？
java – 针对内部类与静态嵌套类的GC性能
望理解这个原因的人能够告诉我原因，不胜感激，谢谢。
如果有错误，请阅读者评论指出，不胜感激。