java - 如何递归地从通用列表中获取范围内的所有元素?
问题描述
给定一个泛型类型列表(List),以及两个泛型类型对象:a,b:
- 设计一个算法,返回一个列表,该列表包含原始列表中属于范围 [a,b) 的每个元素。
- 算法必须包含比较器 E。
- 解决方案必须是“分而治之”算法。
这就是我想出的:
private static <E extends Comparable<E>> List <E> Dominio(List<E> lista, E a, E b){
return DominioAux(lista,a,b,0,lista.size()-1);
}
private static <E extends Comparable<E>> List <E> DominioAux(List<E> lista, E a, E b,Integer i, Integer j){
List<E> res = new ArrayList<>();
Integer m = (j-i)/2;
E pm = lista.get(m);
if (pm == a) {
DominioAux(lista,a,b,m,j);
} else if(pm==b) {
DominioAux(lista,a,b,i,m-1);
}
if (pm.compareTo(a)<0) {
res = DominioAux(lista,a,b,m,j);
}
if (pm.compareTo(a)>0) {
res = DominioAux(lista,a,b,i,m);
}
res = lista.subList(i, j);
return res;
}
问题是当执行其中一个 if 时,我要么得到“索引越界异常”,要么得到“堆栈溢出错误”。
解决方案
一种使用分而治之范式的可能解决方案
private static <E extends Comparable<E>> List <E> DominioAux(List<E> lista, E a, E b,Integer i, Integer j){
List<E> res = new ArrayList<>();
if(i >= j) { //Check if the value of list[i] is in the range [a,b)
if (lista.get(i).compareTo(a) >= 0 && lista.get(i).compareTo(b) < 0) {
res.add(lista.get(i));
}
return res;
}
Integer m = (i + j) / 2;
List<E> list1 = DominioAux(lista, a, b, i, m);
List<E> list2 = DominioAux(lista, a, b, m + 1, j);
res.addAll(list1);
res.addAll(list2);
return res;
}
您的方法中的一个错误是在计算 m 时,如果 i 和 j 则 m 应该是中间值,那么要计算它,您必须添加 i 和 j 而不是从 j 中减去 i
推荐阅读
- docker - 如果容器已经存在,则需要 pod
- r - 如何使用 DAAG 包在 R 中执行重复的 k 折交叉验证?
- linux - sd_journal_print 未正确记录
- apache - Apache 拒绝连接
- javascript - 为什么选择选项没有显示数字?
- blazor-server-side - 未找到 Blazor 路线 - 如何前往站点基地?
- spring-boot - Spring Boot + WebFlux。如何显示一个简单的 index.jsp?
- javascript - 运行反应应用程序时出现 Chokidar UNKNOWN 错误
- mongodb - 在 webapp 中嵌入 CSV 文件或连接到 MongoDB 更好吗?
- css - How do I get webkit styling to work with Vue.js?