大佬们，假设下面这个是已经排序过的关于时间的数组，现在需要添加到不同距离当前年份时间的数组，能用二分查找去实现吗？

[unregister]

public void test(){ String time2 = "2022-08-31"; for(int i = 0; i<times.size();i++){ String time = times.get(i); if(betweenMonth(time,time2) < 12){ oneYearTimes.add(time); } else if(betweenMonth(time,time2) >= 12 && betweenMonth(time,time2) < 24 ){ one2twoYearTimes.add(time); } else if(betweenMonth(time,time2) >= 24 && betweenMonth(time,time2) < 36 ){ two2threeYearTimes.add(time); } else if(betweenMonth(time,time2) >= 36 && betweenMonth(time,time2) < 48 ){ three2fourYearTimes.add(time); } else if(betweenMonth(time,time2) >= 48 && betweenMonth(time,time2) < 48 ){ four2fiveYearTimes.add(time); } else if(betweenMonth(time,time2) >= 60 ){ moreThanFiveYearTimes.add(time); } } }

static Long betweenMonth(String time1, String time2){
    return ChronoUnit.MONTHS.between(parse(time1), parse(time2));
}

static LocalDate parse(String str){
    DateTimeFormatter df = DateTimeFormatter.ofPattern("yyyy-MM-dd");
    return LocalDate.parse(str, df);
}

能不能利用分治的思想。。先给时间排序，然后取中间值，递归下去这样。除了临界点算一下年份之外，其他的 item 都不计算直接存放到数组里面。

[JasonLaw]

建议你补全并格式化一下代码，描述清楚你的问题。

[unregister]

就是根据两个日期的之间相隔的月份，存放到距离 2022-08-31 这个时间点 相差不同年份的数组中。

[unregister]

@JasonLaw 好滴，现在就是需要从一个包含很多时间的集合 times ，根据当前的时间判断距离现在多少年，比如< 12 个月就是一年内，12 - 24 个月存放到 1-2 年的数组中，大于 60 个月的统统都算 5 年以上，这个编辑操作不太会，下面是重新整理过的代码 https://pastebin.com/Vjev1xac 。

[JasonLaw]

@unregister #3 如果我没理解错的话，你就是想要减少 if, else if 的次数，对吧？

[JasonLaw]

@JasonLaw #4 如果是的话，你完全可以使用数组来存储，然后计算`month_diff/12`来决定是存储在那个 index 。

[wxf666]

伪代码：

时间段数组 = [一年时间表，一至两年时间表，二至三，三至四，四至五，五以上];

for 待分类时间 in 待分类时间表
　时间段数组[max(betweenMonth(待分类时间, "2022-08-31") / 12, 时间段数组.size() - 1)].add(待分类时间);


这样？

[wxf666]

写错了，max 改为 min

[unregister]

@JasonLaw 也不完全是啦，就是 if else 里面 不是需要计算相差的月份吗？如果这种写法的话 100 万数据的话，需要比较将近 200 万次。这样性能就很差，就想看看有没有能够减少比较次数的方法。

[unregister]

@wxf666 这个方法挺好的，感觉比较优雅。

[JasonLaw]

@unregister #8 你可以理解计算相差月份是需要常量时间的。我不太理解你所说的“ 100 万数据的话，需要比较将近 200 万次”。

[unregister]

@JasonLaw 就是 betweenMonth 这个方法中，两个日期需要做一次减法操作，else if 里面 需要计算两次日期差 ，那就是接近 200 万次的计算量了。

[zmal]

写个返回 time 距今几个 12 月的函数，stream 流用该函数分组，再用 treemap 搜集。

[unregister]

@zmal 能不能利用分治的思想。。先给时间排序，然后取中间值，递归下去这样。除了临界点算一下年份之外，其他的 item 都不计算直接存放到数组里面。

[JasonLaw]

@unregister #11 其实你说的这些在时间复杂度上面没有多大区别，都是θ(len(times))，因为每次循环最后运算 6 次，我说的方法就是把 6 次变为 1 次。

[zmal]

一次遍历的时间复杂度是 N 。
排序的时间复杂度是 N*logN ，排序再二分还得*logN ，你咋想的大兄弟。

[JasonLaw]

@unregister #13 将 times 进行排序就需要θ(nlgn)了🤕。我很想知道你是怎么做到“ 除了临界点算一下年份之外，其他的 item 都不计算直接存放到数组里面”的，写一下代码或伪代码让我看一下，我真的很想知道。

[zmal]

我明白你的意思了，你是觉得你的一坨 if else 代码需要比较 6 次有多余耗时？其实优化成 除 12 再分组就可以了。
而且计算时间复杂度时常数的部分可以忽略。而且大于小于这种计算在这个场景里的时间消耗可以忽略不计。

[unregister]

@zmal 哈哈哈哈，看来我之前没整明白。
@JasonLaw 😅，看来我之前没整的很清楚，代码实现的有问题，有点"急“了，希望大佬包涵一下。

[unregister]

@zmal 嗯嗯好的，我在去测试一下。

[JasonLaw]

@zmal #12 不太懂为什么要用 tree map ，OP 的源代码应该没这样的需求，更重要的是，涉及到排序的话，时间复杂度就是 O(nlgn)了，而且 hash table 会用到更多的 memory ，计算 index 也会更加耗时。如果我说错的话，欢迎指出。

[JasonLaw]

@unregister #18 我不是大佬，我还是在一直学习。如果你想要更加理解代码的话，真的建议你学习一下算法和数据结构，https://neetcode.io/是个好地方，我也在使用这个网站，大家一起进步。

[aguesuka]

首先你的代码应该是这样, 也就是先把重复的代码抽离成方法.

public void test() {
String time2 = "2022-08-31";
for (int i = 0; i < times.size(); i++) {
String time = times.get(i);
var monthsBetween = betweenMonth(time, time2);
findTimeList(monthsBetween).add(time);
}
}

List<String> findTimeList(long monthsBetween){
// TODO
}

[zmal]

@JasonLaw
private int 返回入参时间距今几年(String time);
Map<Integer, List<String>> yearMap = list.stream().collect(Collectors.groupingBy(this::返回入参时间距今几年, TreeMap::new, Collectors.toList()));

treeMap 只是用来把年份做个排序，遍历的时候方便。不用也可以。

[msg7086]

你想把扫全表变成二分搜来做 grouping 是吗？

确实可以做的。

比如说 Ruby 里有 bsearch_index 可以通过条件在数组里做二分搜，返回第一个满足条件的项的下标。
假设 times 是时间数组，降序，time2 是比较日期
year2_date = time2 - 1.year
year2_idx = times.bsearch_index {|time| time < year2_date} #找到第一个 1 年以前的日期
year3_date = time2 - 2.year
year3_idx = times.bsearch_index {|time| time < year3_date} #找到第一个 2 年以前的日期
然后把 0-year2_idx 的和 year2_idx-year3_idx 等等的 slice 切出来放进不同数组就行了。

[JasonLaw]

@zmal #23 有一个疑问，使用 tree map 的话，时间复杂度是 O(nlgn)，对吗？

[zmal]

@JasonLaw
？？？ treeMap 的 key 是 int 值的年份，总共才 5 个数，和时间集合的长度无关。

[JasonLaw]

@zmal #26 对，如果不包含所有年份差的话，就是只有 6 个 key 。

[unregister]

@JasonLaw Thank you,已经收藏啦
@aguesuka 学习了。
@msg7086 谢谢大佬的思路。