題目

給定一組范圍在00：00至23：59的時間，求任意兩個時間之間的最小時間差。例如，輸入時間數(shù)組[“23：50”，“23：59”，“00：00”]，"23：59"和"00：00"之間只有1分鐘的間隔，是最小的時間差。

分析

這個題目最直觀的解法是求出任意兩個時間的間隔，然后比較得出最小的時間差。如果輸入n個時間，那么需要計(jì)算每個時間與另外n-1個時間的間隔，這種蠻力法需要O（n2）的時間。

上述解法的一個優(yōu)化方法是把n個時間排序。排序之后只需要計(jì)算兩兩相鄰的時間之間的間隔，這樣就只需要計(jì)算O（n）個時間差。由于對n個時間進(jìn)行排序通常需要O（nlogn）的時間，因此這種優(yōu)化算法的總體時間復(fù)雜度是O（nlogn）。

這里有一個特殊情況值得注意。如果把輸入的時間數(shù)組[“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分鐘。也就是說，在計(jì)算最小時間差時，需要把排序之后的第1個時間當(dāng)作第2天的時間（即加上24小時）與最后一個時間之間的間隔也考慮進(jìn)去。

接著思考如何做進(jìn)一步優(yōu)化。前面的算法主要將時間花在排序上面，那么排序是否可以避免？排序是為了計(jì)算相鄰的兩個時間的節(jié)點(diǎn)，所以用一個表示時間的數(shù)組也可以達(dá)到這個目的。

一天有24小時，即1440分鐘。如果用一個長度為1440的數(shù)組表示一天的時間，那么數(shù)組下標(biāo)為0的位置對應(yīng)時間00：00，下標(biāo)為1的位置對應(yīng)時間00：01，以此類推，下標(biāo)為1439的位置對應(yīng)23：59。數(shù)組中的每個元素是true或false的標(biāo)識，表示對應(yīng)的時間是否存在于輸入的時間數(shù)組中。

有了這個輔助數(shù)組，就只需要從頭到尾掃描一遍，相鄰的兩個為true的值表示對應(yīng)的兩個時間在輸入時間數(shù)組中是相鄰的。例如，輸入時間數(shù)組[“23：50”，“23：59”，“00：00”]，數(shù)組中只有下標(biāo)為0、1430和1439這3個位置的值為true，其他位置的值都是false。

由于數(shù)組的下標(biāo)對應(yīng)的是時間，因此兩個時間之間的時間差就是它們在數(shù)組中對應(yīng)的下標(biāo)之差。23：50和23：59之間相隔9分鐘，它們在數(shù)組中的下標(biāo)之差也是9。文章來源地址http://www.zghlxwxcb.cn/news/detail-740849.html

解

public class Test {
    public static void main(String[] args) {
        List<String> timePoints = Arrays.asList("23:50", "23:59", "00:00");
        int result = findMinDifference(timePoints);
        System.out.println(result);
    }

    public static int findMinDifference(List<String> timePoints) {
        if (timePoints.size() > 1440) {
            return 0;
        }

        boolean[] minuteFlags = new boolean[1440];
        for (String time : timePoints) {
            String[] t = time.split(":");
            int min = Integer.parseInt(t[0]) * 60 + Integer.parseInt(t[1]);
            if (minuteFlags[min]) {
                return 0;
            }

            minuteFlags[min] = true;
        }

        return helper(minuteFlags);
    }

    private static int helper(boolean[] minuteFlags) {
        int minDiff = minuteFlags.length - 1;
        int prev = -1;
        int first = minuteFlags.length - 1;
        int last = -1;
        for (int i = 0; i < minuteFlags.length; i++) {
            if (minuteFlags[i]) {
                if (prev >= 0) {
                    minDiff = Math.min(i - prev, minDiff);
                }

                prev = i;
                first = Math.min(i, first);
                last = Math.max(i, last);
            }
        }

        minDiff = Math.min(first + minuteFlags.length - last, minDiff);
        return minDiff;
    }
}

到了這里，關(guān)于面試算法35：最小時間差的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！