《剑指 Offer》专项突破版 - 面试题 35 : 最小时间差（两种方法 + C++ 实现）

目录

前言

一、排序

二、数组

前言

题目链接：LCR 035. 最小时间差 - 力扣（LeetCode）

题目：

给定一组范围在 00:00 至 23:59 的时间，求任意两个时间之间的最小时间差（以分钟数表示）。例如，输入数组 ["23:50", "23:59", "00:00"]，"23:59" 和 "00:00" 之间只有 1 分钟的间隔，是最小的时间差。

分析：

这个题目最直观的解法是求出任意两个时间的间隔，然后比较得出最小的时间差。如果输入n个时间，那么这种蛮力法需要 O(n^2) 的时间。

一、排序

上述解法的一个优化方法是把 n 个时间排序。排序之后只需要计算两两相邻的时间之间的间隔，这样就只需要计算 O(n) 个时间差。由于对 n 个时间进行排序通常需要 O(nlogn) 的时间，因此这种优化算法的总体时间复杂度是 O(nlogn)。

这里有一个特殊情况值得注意。如果把输入的时间数组 ["23:50", "23:59", "00:00"] 排序，就可以得到 ["00:00", "23:50", "23:59"]。时间 00:00 和 23:50 之间的间隔是 1430 分钟，而 23:50 和 23:59 之间的间隔是 9 分钟。由于排序之后的第 1 个 00:00 也可能是第 2 天的 00:00，它和前一天的 23:59 之间的间隔只有 1 分钟。也就是说，在计算最小时间差时，需要把排序之后的第 1 个时间当作第 2 天的时间（即加上 24 小时）与最后一个时间之间的间隔也考虑进去。

class Solution {
public:
    int findMinDifference(vector<string>& timePoints) {
        if (timePoints.size() > 24 * 60)  // 说明存在相同的时间点
            return 0;
​
        sort(timePoints.begin(), timePoints.end());
        int minDiff = INT_MAX;
        int prevMinute = stoi(timePoints[0].substr(0, 2)) * 60 + stoi(timePoints[0].substr(3));
        int tmp = prevMinute;
        for (size_t i = 1; i < timePoints.size(); ++i)
        {
            int curMinute = stoi(timePoints[i].substr(0, 2)) * 60 + stoi(timePoints[i].substr(3));
            if (curMinute - prevMinute < minDiff)
                minDiff = curMinute - prevMinute;
​
            prevMinute = curMinute;
        }
        // 特殊情况
        if (tmp + 24 * 60 - prevMinute < minDiff)
            minDiff = tmp + 24 * 60 - prevMinute;
​
        return minDiff;
    }
};

二、数组

接着思考如何做进一步优化。前面的算法主要将时间花在排序上面，那么排序是否可以避免？排序是为了计算相邻的两个时间的节点，所以用一个表示时间的数组也可以达到这个目的。

一天有 24 小时，即 1440 分钟。如果用一个长度为 1440 的数组表示一天的时间，那么数组下标为 0 的位置对应时间 00:00，下标为 1 的位置对应时间 00:01，以此类推，下标为 1439 的位置对应 23:59。数组中的每个元素是 true 或 false 的标识，表示对应的时间是否存在于输入的时间数组中。

有了这个辅助数组，就只需要从头到尾扫描一遍，相邻的两个为 true 的值表示对应的两个时间在输入数组中是相邻的。例如，输入时间数组 ["23:50", "23:59", "00:00"]，数组中只有下标为 0、1430 和 1439 这 3 个位置的值为 true，其他位置的值都是 false。

由于数组的下标对应的是时间，因此两个时间之间的时间差就是它们在数组中对应的下标之差。23:50 和 23:59 之间相隔 9 分钟，它们在数组中的下标之差也是 9。

class Solution {
public:
    int findMinDifference(vector<string>& timePoints) {
        if (timePoints.size() > 1440)
            return 0;
        
        vector<bool> minuteFlags(1440, false);
        for (const string& t : timePoints)
        {
            int minute = stoi(t.substr(0, 2)) * 60 + stoi(t.substr(3));
            if (minuteFlags[minute])
                return 0;
            
            minuteFlags[minute] = true;
        }
​
        int minDiff = INT_MAX;
        int prevMinute = -1;
        int firstMinute = INT_MAX;
        int lastMinute = -1;
        for (int i = 0; i < 1440; ++i)
        {
            if (minuteFlags[i])
            {
                if (prevMinute >= 0)
                {
                    if (i - prevMinute < minDiff)
                        minDiff = i - prevMinute;
                }
​
                prevMinute = i;
                if (i < firstMinute)
                    firstMinute = i;
                
                if (i > lastMinute)
                    lastMinute = i;
            }
        }
        // 特殊情况
        if (firstMinute + 1440 - lastMinute < minDiff)
            minDiff = firstMinute + 1440 - lastMinute;
        
        return minDiff;
    }
};

该算法的时间复杂度是 O(n)，空间复杂度是 O(1)。