LeetCode 1057 Campus Bikes

思路

思路：使用priority queue并且重写比较器，(o1,o2)：当需要递增/最小堆时，o1<o2:-1;递减/最大堆时，o1-o2:1. 然后根据给出的条件构造每一个Triple然后将其放入pq中。然后在填写result数组时，要先判断poll出来的worker和bike有没有被用过，用过就直接continue，可以使用2个boolean数组来进行判断。

时间复杂度O(NM log(NM))
空间复杂度O(NM)

代码

class Triple {
    int workerIndex;int bikeIndex;int distance;Triple(int workerIndex, int bikeIndex, int distance) {
    this.workerIndex = workerIndex;this.bikeIndex = bikeIndex;this.distance = distance;}
}
class Solution {
    public int[] assignBikes(int[][] workers, int[][] bikes) {
    int[] result = new int[workers.length];PriorityQueue<Triple> pq = new PriorityQueue<Triple>(new Comparator<Triple>() {
    public int compare(Triple t1, Triple t2) {
    if (t1.distance == t2.distance) {
    if (t1.workerIndex == t2.workerIndex) {
    return t1.bikeIndex - t2.bikeIndex;} else {
    return t1.workerIndex - t2.workerIndex;}} else {
    return t1.distance - t2.distance;}}});boolean[] workerUsed = new boolean[workers.length];boolean[] bikeUsed = new boolean[bikes.length];for (int i = 0; i < workers.length; i++) {
    for (int j = 0; j < bikes.length; j++) {
    int dist = Math.abs(workers[i][0] - bikes[j][0])+ Math.abs(workers[i][1] - bikes[j][1]);pq.offer(new Triple(i, j, dist));}}while (!pq.isEmpty()) {
    Triple cur = pq.poll();int wIndex = cur.workerIndex, bIndex = cur.bikeIndex;if (workerUsed[wIndex] || bikeUsed[bIndex]) {
    continue;}result[wIndex] = bIndex;workerUsed[wIndex] = true;bikeUsed[bIndex] = true;}return result;}
}