Java TreeSet使用的内存是否少于PriorityQueue？

Question

我正在做这个问题并首先使用PriorityQueue解决了它：-

public ArrayList<Integer> solve(int A, int B, int C, int D) {

    PriorityQueue<Integer> q = new PriorityQueue<>();

    q.add(A);

    q.add(B);

    q.add(C);

    ArrayList<Integer> list = new ArrayList<>();

    while(list.size() < D){

        int val = q.poll();

        if(list.size() == 0 || list.get(list.size() - 1) != val)

        list.add(val);

        q.add(val*A);

        q.add(val*B);

        q.add(val*C);

    }

    list.sort(null);

    return list;

}

但是它给出了java.lang.OutOfMemoryError：Java堆空间错误。

用TreeSet替换PriorityQueue后，该解决方案被接受：-

 public ArrayList<Integer> solve(int A, int B, int C, int D) {

    ArrayList<Integer> res = new ArrayList<>() ;

    TreeSet<Integer> set = new TreeSet<>() ;

    set.add(A) ;

    set.add(B) ;

    set.add(C) ;

    for(int i = 0; i < D; i++) {

        int temp = set.first() ;

        set.remove(temp) ;

        res.add(temp) ;

        set.add(temp*A) ;

        set.add(temp*B) ;

        set.add(temp*C) ;

    }

    return res ;

}

Answer 1

它与数据结构无关。第一种情况的参数组合可能导致此语句永远不成立：if(list.size()&nbsp;==&nbsp;0&nbsp;||&nbsp;list.get(list.size()&nbsp;-&nbsp;1)&nbsp;!=&nbsp;val)这意味着循环永远不会终止，并且对象q会增长，直到内存用尽。例如，尝试使用以下命令进行呼叫：solve(1,1,2,5)在这种情况下，两个数据结构之间的内存差异没有影响。需要注意的是与随机访问和下一个/上一个指针有关的一些差异，但这与此处无关。

Answer 2

基本上，它与使用的内存量无关，只是您的程序永PriorityQueue无休止地使用，不断增加元素PriorityQueue。它不会结束，因为您的条件if(list.size() == 0 || list.get(list.size() - 1) != val)-它永远不会满足，因此检查list（永远不会改变）大小的while循环始终为true，因此每个循环执行都从队列中提取1个元素，然后添加3个元素做到这一点。