MinimumTimeDifference [source code]
public class MinimumTimeDifference {
static
/******************************************************************************/
class Solution {
public int findMinDifference(List<String> timePoints) {
boolean[][] points = new boolean[24][60]; //[0-23][0-59]
for (String timePoint : timePoints) {
String[] tokens = timePoint.split("\\:");
int hour = Integer.parseInt(tokens[0]), minute = Integer.parseInt(tokens[1]);
if (points[hour][minute])
return 0;
points[hour][minute] = true;
}
int min = Integer.MAX_VALUE, prev[] = {-1, -1};
for (int i = 0; i < 48; i++) {
for (int minute = 0; minute < 60; minute++) {
int hour = i % 24;
if (points[hour][minute]) {
if (prev[0] < 0) {
prev[0] = hour;
prev[1] = minute;
} else {
int distance = (hour * 60 + minute) - (prev[0] * 60 + prev[1]);
if (distance < 0)
distance += 24 * 60;
min = Math.min(min, distance);
prev[0] = hour;
prev[1] = minute;
}
}
}
}
return min;
}
}
/******************************************************************************/
public static void main(String[] args) {
MinimumTimeDifference.Solution tester = new MinimumTimeDifference.Solution();
String[][] inputs = {
{"23:59","00:00"}, {"1"},
{"00:00","23:59","00:00"}, {"0"},
{"12:12","12:13"}, {"1"},
};
for (int i = 0; i < inputs.length / 2; i++) {
List<String> timePoints = Arrays.asList(inputs[2 * i]);
int ans = Integer.parseInt(inputs[1 + 2 * i][0]);
System.out.println(Printer.separator());
int output = tester.findMinDifference(timePoints);
System.out.println(
Printer.wrapColor(timePoints.toString(), "magenta") +
" -> " + output +
Printer.wrapColor(", expected: " + ans, ans == output ? "green" : "red")
);
}
}
}
先想一下笨办法怎么做? 首先这里的这个distance是什么样的一个定义? 如果给你两个时间点, 你怎么计算? 事实上, 这个distance是一个cyclic的定义, 而且两个时间点计算之间的举例好像并不仅是一个cyclic的问题, 因为即便是cyclic, 也是有两个方向的. 不过应该还是有办法计算的, 大不了两个方向取min. 那么笨办法其实就是, 所有的pair generate出来, 然后找到一个最大值. 这个是一个N^2的算法;
想要加速到O(N), 这个题目感觉历史信息流好像可以用. 因为比如A和B两个时间点的距离你知道了, 再来一个C, 你知道了(A,C), 你也就知道了(B,C). 大概画图看了一下, 好像这个问题其实一个sort就解决了? NlgN的速度也可以了, 先写这个算法算了; 不对, 这里这个sort不需要NlgN? 可不可以用hashing?
另外, 这个题目刚读完的时候, 我就发现有一个地方他没有澄清: 是否允许duplicate(这个问题当你看到array类的题目的时候始终应该脑子里有一根弦); 果然, 最后这个问题是一个坑;
这个题目总体其实还是很简单的, 不过最后花的时间有点多, 最后的速度是19ms (75%), 还可以; 这个做法最后应该是O(N)的;
在做的时候涉及到几个经验:
- 这个问题因为涉及到cyclic distance所以脑子里有一个表盘的visual是很好的; 不过visual的时候记得不要分针. 一个时间点, 无论精确到minute还是second, 最后对应的其实就是时针的一个点, 不需要有分针和秒针;
- 这里处理cyclic的另外一个技巧就是最后所有的时间点要循环两次就行, 这个也是之前题目的时候碰到过的一个技巧; 如果不熟悉了, 可以大概脑子里想一下为什么这样一个做法就可以了;
- 在cyclic计算distance的时候, 我们计算的实际上是所有的相邻时间点的距离; 计算的时候, 只要保证是从前一个时间点到后一个时间点(前后按sort后的顺序定义)的distance就行, 而不需要计算两个方向的距离的最小值: 因为我们大循环循环两次, 所以假设只有3:00和21:00这两个点, 最后3:00->21:00和21:00->3:00两个方向是都会被计算到的, 所以不用担心; 假如这两个点之间还掺杂了其他的点, 就更不用管了, 比如加上一个0:00, 那么最后只有一个方向的作数;
- 在distance计算的时候, 还是用例子来思考; 我用的例子是22:10和0:15. 刚开始还考虑什么补足的算法, 后来发现其实很简单, 直接化成minute相减, 然后如果<0了, 直接一个base加上去就行了;
discussion最优解, 思路几乎跟我的一模一样(不过我还是满欣赏我自己的thinking process的), 不过他所有的处理全都一维化了;
public class Solution {
public int findMinDifference(List<String> timePoints) {
boolean[] mark = new boolean[24 * 60];
for (String time : timePoints) {
String[] t = time.split(":");
int h = Integer.parseInt(t[0]);
int m = Integer.parseInt(t[1]);
if (mark[h * 60 + m]) return 0;
mark[h * 60 + m] = true;
}
int prev = 0, min = Integer.MAX_VALUE;
int first = Integer.MAX_VALUE, last = Integer.MIN_VALUE;
for (int i = 0; i < 24 * 60; i++) {
if (mark[i]) {
if (first != Integer.MAX_VALUE) {
min = Math.min(min, i - prev);
}
first = Math.min(first, i);
last = Math.max(last, i);
prev = i;
}
}
min = Math.min(min, (24 * 60 - last + first));
return min;
}
}
但是他的另外一个差别就是他没有iterate两次, 而是最后专门加了一个last和first的处理; 也行吧, 只能说, 更加less general, but works for the problem;
另外一个观点:
@jdrogin said in Verbose Java Solution, Bucket:
same idea here but you can improve your time a little if you avoid string split and int parse. You know the input format so you can leverage that directly. Also I break out the wrap around time difference rather than doing it in the same loop.
public int FindMinDifference(IList<string> timePoints) {
bool[] axis = new bool[24 * 60];
foreach (string t in timePoints)
{
int hour = 10 * (t[0] - '0') + (t[1] - '0');
int minute = 10 * (t[3] - '0') + (t[4] - '0');
int index = hour * 60 + minute;
if (axis[index]) return 0; // duplicate
axis[index] = true;
}
int min = axis.Length;
int curr = axis.Length;
for (int i = 0; i < axis.Length; i++)
{
if (axis[i])
{
if (curr < min) min = curr;
curr = 1;
}
else
{
curr++;
}
}
// now check wrap around time diff
int dist = 1;
int first = 0;
while (!axis[first]) { first++; dist++; }
int last = axis.Length - 1;
while (!axis[last]) { last--; dist++; }
if (dist < min) min = dist;
return min;
}
避免了使用split, 是一个想法; regex的东西确实有一定的速度代价;
这个是另外一个思路:
@cdai said in Verbose Java Solution, Bucket:
Thanks for sharing! Can we make use of radix sorting here to decrease the space complexity?
public int findMinDifference(List<String> timePoints) {
int n = timePoints.size();
int[] ts = new int[n];
for (int i = 0; i < n; i++) { // Convert date to minutes format
String[] hhmm = timePoints.get(i).split(":");
ts[i] = Integer.valueOf(hhmm[0]) * 60 + Integer.valueOf(hhmm[1]);
}
for (int d = 0; d < 4; d++) { // Perform radix sorting
ts = countingSort(ts, d);
}
int min = Integer.MAX_VALUE;
for (int i = 1; i < n; i++) { // Compare adjacent time
min = Math.min(min, ts[i] - ts[i - 1]);
}
min = Math.min(min, 1440 - (ts[n - 1] - ts[0]));
return min;
}
private int[] countingSort(int[] ts, int d) {
// Count number of occurance of each digit
int[] cnt = new int[10];
for (int t : ts) {
for (int i = 0; i < d; i++) t /= 10; // Get digit value
cnt[t % 10]++;
}
// Add up number of occurance into position in final output
for (int i = 1; i < cnt.length; i++) cnt[i] += cnt[i - 1];
// Place each number on its position
int n = ts.length;
int[] ret = new int[n];
for (int i = n - 1; i >= 0; i--) {
int t = ts[i];
for (int j = 0; j < d; j++) t /= 10;
ret[--cnt[t % 10]] = ts[i]; // off-by-one
}
return ret;
}
用的是radix sort, 或者说counting sort, 这个是我当时学的不太熟悉的一个算法, 不过看这里代码的写法, 好像更Sedgwick上面写的差不多; 第三个循环就有点看不懂了; 想想loop var是怎么被使用的; 大概知道点意思, 不过具体的correctness还是有点模糊了, 后面复习一下之后再说了;
我换掉了两次循环的做法, 改成这样:
class Solution {
public int findMinDifference(List<String> timePoints) {
boolean[][] points = new boolean[24][60]; //[0-23][0-59]
for (String timePoint : timePoints) {
String[] tokens = timePoint.split("\\:");
int hour = Integer.parseInt(tokens[0]), minute = Integer.parseInt(tokens[1]);
if (points[hour][minute])
return 0;
points[hour][minute] = true;
}
int min = Integer.MAX_VALUE, prev[] = {-1, -1};
int first = -1, last = -1;
for (int hour = 0; hour < 24; hour++) {
for (int minute = 0; minute < 60; minute++) {
if (points[hour][minute]) {
if (first < 0)
first = hour * 60 + minute;
if (prev[0] < 0) {
prev[0] = hour;
prev[1] = minute;
} else {
int distance = (hour * 60 + minute) - (prev[0] * 60 + prev[1]);
if (distance < 0)
distance += 1440;
min = Math.min(min, distance);
prev[0] = hour;
prev[1] = minute;
}
last = hour * 60 + minute;
}
}
}
min = Math.min(min, (first - last + 1440) % 1440);
return min;
}
}
结果速度还变慢了(21ms), 不知道为什么; 可能最后还是这个二维化的原因?
如果不拘泥于O(N)的时间, 这个问题的sort甚至可以直接在string的基础上做:
public int findMinDifference(List<String> timePoints) {
Collections.sort(timePoints);
int minDiff = Integer.MAX_VALUE;
String prev = timePoints.get(timePoints.size()-1);
for (String s : timePoints) {
int prevMins = Integer.parseInt(prev.split(":")[0])*60 + Integer.parseInt(prev.split(":")[1]);
int curMins = Integer.parseInt(s.split(":")[0])*60 + Integer.parseInt(s.split(":")[1]);
int diff = curMins - prevMins;
if (diff < 0) diff += 1440;
minDiff = Math.min(minDiff, Math.min(diff, 1440 - diff));
prev = s;
}
return minDiff;
}
倒不是说这个思路更好, 提供一个新的思考角度而已;
另外, 这个人还认为hashing(也有人说pigeonhole)的做法其实空间复杂度可以认为是O(1). 这个好像是对的! 那么前面那个radix sort的做法是否可以完成空间复杂度的降低呢? 事实上还是可以的, 因为我们这里有一个特例, 就是如果duplicate就立刻return 0, 所以最后radix sort的做法虽然空间复杂度是根据input list给了多少个时间点来决定的, 但是我们这里这个number of timePoints是有一个上限的(还有一个原因是因为精度只到minute), 所以最后radix sort的做法其实也是O(1)的空间, 而且同时比直接hashing/bucket sort要好;
Problem Description
Given a list of 24-hour clock time points in "Hour:Minutes" format, find the minimum minutes difference between any two time points in the list.
Example 1:
Input: ["23:59","00:00"]
Output: 1
Note:
- The number of time points in the given list is at least 2 and won't exceed 20000.
- The input time is legal and ranges from 00:00 to 23:59.
Difficulty:Medium
Total Accepted:10.1K
Total Submissions:22.2K
Contributor: fallcreek
Companies
palantir
Related Topics
string