LeetCode 1094.拼车。什么是时间复杂度？

Question

我目前正处于面试准备周期，最近一直在加速。问题是：

LeetCode 1094

我无法理解这个问题的时间复杂度。这是我的代码：

class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        HashMap<Integer, List<Integer>> dropOff = new HashMap<>();
        HashMap<Integer, List<Integer>> pickUp = new HashMap<>();
        
        int endLocation = 0;
        for (int i = 0; i < trips.length; i++) {
            int peopleToAdd = trips[i][0];
            
            //get current values from map
            List<Integer> peopleToGet=pickUp.getOrDefault(trips[i][1], new ArrayList<>());
            List<Integer> peopleToDrop=dropOff.getOrDefault(trips[i][2],new ArrayList<>());
            
            //add group to list of people being dropped/added at a stop
            peopleToGet.add(peopleToAdd);
            peopleToDrop.add(peopleToAdd)
            ;
            pickUp.put(trips[i][1], peopleToGet);
            dropOff.put(trips[i][2], peopleToDrop);
            endLocation = Math.max(endLocation, trips[i][2]);
        }
        
        int currentCapacity = 0;
        for (int i = 1; i <= endLocation; i++) {
            if (pickUp.containsKey(i)) {
                List<Integer> key = pickUp.get(i);
                for (int temp : key) {
                    currentCapacity += temp;
                }
            }
            if (dropOff.containsKey(i)) {
                List<Integer> key = dropOff.get(i);
                for (int temp : key) {
                    currentCapacity -= temp;
                }
            }
            
            if (currentCapacity > capacity) return false;
        }
        
        return true;
        
        
    }
}

嵌套的 for-lop 总是让我想到 n^2，但如果你考虑这个问题，每个队列都有一个上车和一个下车。所以，您实际上是在进行 2N 次计算，其中 N 是同类群组的数量。您还遍历了所有可能的停靠点。

谢谢。

Answer 1

我猜你的时间复杂度是 O(N ^ 2):

• O(N) 循环
  • O(N) 为 Math.max()

虽然我可能是错的。

---

我们可以使用 TreeMap，它有一个 O(Log N) get 方法并将时间复杂度降低到 O(N Log N)，内存复杂度为 O(N):

class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        TreeMap<Integer, Integer> treemap = new TreeMap<>();

        for (int[] trip : trips) {
            treemap.put(trip[1], treemap.getOrDefault(trip[1], 0) + trip[0]);
            treemap.put(trip[2], treemap.getOrDefault(trip[2], 0) - trip[0]);
        }

        for (int passenger : treemap.values()) {
            capacity -= passenger;

            if (capacity < 0) {
                return false;
            }
        }

        return true;
    }
}

渐近地，遍历数组一次或十亿次都没有关系，两者都是 N 时间复杂度的数量级：

O(10 * e9 N) == O(N)

---

你的代码看起来不错，一点也不差。只需确保：

• 保持间距一致
• 将所有内容写在单独的一行中
• 始终添加 {}，即使单行 if 或 for.
不需要添加

class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        HashMap<Integer, List<Integer>> dropOff = new HashMap<>();
        HashMap<Integer, List<Integer>> pickUp = new HashMap<>();

        int endLocation = 0;

        for (int i = 0; i < trips.length; i++) {
            int peopleToAdd = trips[i][0];

            //get current values from map
            List<Integer> peopleToGet = pickUp.getOrDefault(trips[i][1], new ArrayList<>());
            List<Integer> peopleToDrop = dropOff.getOrDefault(trips[i][2], new ArrayList<>());

            //add group to list of people being dropped/added at a stop
            peopleToGet.add(peopleToAdd);
            peopleToDrop.add(peopleToAdd);
            pickUp.put(trips[i][1], peopleToGet);
            dropOff.put(trips[i][2], peopleToDrop);
            endLocation = Math.max(endLocation, trips[i][2]);
        }

        int currentCapacity = 0;

        for (int i = 1; i <= endLocation; i++) {
            if (pickUp.containsKey(i)) {
                List<Integer> key = pickUp.get(i);

                for (int temp : key) {
                    currentCapacity += temp;
                }
            }

            if (dropOff.containsKey(i)) {
                List<Integer> key = dropOff.get(i);

                for (int temp : key) {
                    currentCapacity -= temp;
                }
            }

            if (currentCapacity > capacity) {
                return false;
            }
        }

        return true;

    }
}

祝你面试顺利！！

---

参考资料

• 更多详情，您可以查看Discussion Board。有很多公认的解决方案、解释、各种语言的高效算法，以及 time/space 复杂性分析。