前端之家

  1. 首页
  2. 问答

如何从通用列表递归获取范围内的所有元素？

• 问答

给出一个通用类型列表（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,lista.size()-1);
}

private static <E extends Comparable<E>> List <E> DominioAux(List<E> lista,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,m,j);
    } else if(pm==b) {
        DominioAux(lista,i,m-1);
    }

    if (pm.compareTo(a)<0) {
        res = DominioAux(lista,j);
    }   

    if (pm.compareTo(a)>0) {
        res = DominioAux(lista,m);
    }

    res = lista.subList(i,j);
    return res;     
}

问题是当执行其中一个if时，我得到了“索引超出范围异常”或“堆栈溢出错误”。

lykccz 回答：如何从通用列表递归获取范围内的所有元素？

使用分而治之范式的一种可能的解决方案

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,m + 1,j);

    res.addAll(list1);
    res.addAll(list2);

    return res;
}

您的方法中的一个错误是，在计算m时，如果i和j被认为是m的中间值，则必须将i和j相加而不要从j中减去i

divide-and-conquergeneric-listgeneric-type-argumentjavalist
本文链接：https://www.f2er.com/3023260.html

大家都在问