给定数字能组成的最大时间
难度:
标签:
题目描述
代码结果
运行时间: 20 ms, 内存: 16.0 MB
/*
* 给定一个由 4 位数字组成的数组,返回可以设置的符合 24 小时制的最大时间。
* 24 小时格式为 "HH:MM" ,其中 HH 在 00 到 23 之间,MM 在 00 到 59 之间。
* 最小的 24 小时制时间是 00:00 ,而最大的是 23:59 。从 00:00 (午夜)开始算起,过得越久,时间越大。
* 以长度为 5 的字符串,按 "HH:MM" 格式返回答案。如果不能确定有效时间,则返回空字符串。
*/
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class Solution {
public String largestTimeFromDigits(int[] arr) {
List<int[]> permutations = permute(arr);
String maxTime = "";
for (int[] perm : permutations) {
String HH = "" + perm[0] + perm[1];
String MM = "" + perm[2] + perm[3];
if (HH.compareTo("24") < 0 && MM.compareTo("60") < 0) {
String currentTime = HH + ":" + MM;
if (maxTime.compareTo(currentTime) < 0) {
maxTime = currentTime;
}
}
}
return maxTime;
}
private List<int[]> permute(int[] arr) {
return IntStream.range(0, arr.length)
.boxed()
.flatMap(i -> IntStream.range(0, arr.length)
.filter(j -> j != i)
.boxed()
.flatMap(j -> IntStream.range(0, arr.length)
.filter(k -> k != i && k != j)
.boxed()
.flatMap(k -> IntStream.range(0, arr.length)
.filter(l -> l != i && l != j && l != k)
.mapToObj(l -> new int[] {arr[i], arr[j], arr[k], arr[l]}))))
.collect(Collectors.toList());
}
}
解释
方法:
该题解的思路是使用Python的itertools.permutations来生成数组arr的所有可能的排列组合。每一个排列代表一个时间的尝试,其中排列的前两位数字组合成小时,后两位组合成分钟。然后,这个解决方案会检查每个生成的时间是否符合24小时制的有效时间(即小时数小于24,分钟数小于60)。如果是有效时间,就将其转换成HH:MM的格式,并与之前保存的最大时间进行比较。最后返回最大的有效时间字符串。如果没有找到任何有效的时间,则返回空字符串。
时间复杂度:
O(1)
空间复杂度:
O(1)
代码细节讲解
🦆
如果输入数组中包含重复数字,这种情况下的排列结果会如何影响算法的性能和输出?
▷🦆
在极端情况下(例如所有数字均大于5),此算法返回空字符串的处理是否有效?
▷