肃宁县做网站价格,物流网站建设 市场分析,网站建设合同服务事项,展览展示设计公司首先可以想到#xff0c;可以计算出任意两个时间之间的差值#xff0c;然后比较出最小的#xff0c;不过这种蛮力方法时间复杂度是O(n^2)。而先将时间列表排序#xff0c;再计算相邻两个时间的差值#xff0c;就只需要计算n个差值#xff0c;而排序阶段时间复杂度通常为O… 首先可以想到可以计算出任意两个时间之间的差值然后比较出最小的不过这种蛮力方法时间复杂度是O(n^2)。而先将时间列表排序再计算相邻两个时间的差值就只需要计算n个差值而排序阶段时间复杂度通常为O(nlogn)所以优化后的时间复杂度为O(nlogn)。 不过需要注意的是还需要考虑第一个和最后一个时间点跨越午夜的时间差的大小。并且一天只有1440分钟如果时间列表大于1440那么必然有重复的时间点最小差值即为0。 class Solution {public int findMinDifference(ListString timePoints) {int n timePoints.size();// 由于一天最多有1440分钟如果timePoints超过1440个那么必然有重复的时间点最小差值为0if (n 1440) {return 0;}// 将时间点按字符串排序默认是按HH:MM的字典顺序排序Collections.sort(timePoints);int ans Integer.MAX_VALUE;// 获取第一个时间点的分钟数int t0Minutes getMinutes(timePoints.get(0));// 初始化上一个时间点为第一个时间点int preMinutes t0Minutes;// 从第二个时间点开始逐个计算与前一个时间点的时间差for (int i 1; i n; i) {int minutes getMinutes(timePoints.get(i));// 计算相邻时间点的时间差并保留最小的ans Math.min(ans, minutes - preMinutes); preMinutes minutes; // 更新上一个时间点为当前时间点}// 计算第一个和最后一个时间点跨越午夜的时间差ans Math.min(ans, t0Minutes 1440 - preMinutes);return ans;}// 将时间点转换为分钟数的方法比如输入“1001”返回601public int getMinutes(String t) {return ((t.charAt(0) - 0) * 10 (t.charAt(1) - 0)) * 60 ((t.charAt(3) - 0) * 10 (t.charAt(4) - 0));}
}
