3

问题在于selection algorithm选择总和至少为某个值 N 的最少项目数的变化。例如，您可能想要一个总和为 5,000 或更多的项目列表，但您不想要更多的项目您必须从输入列表中获取。因此，如果一个数字是 5,001，那么您的输出列表将包含一个数字。

另一个例子：Input list {3,4,5,1,2} target = {8}. output list will be : {5,3}。

这个问题已经binaryHeap在这个优秀的系列文章中被证明可以解决；但是当我实现时Java，我没有得到想要的输出。我得到了整个input list. 我无法找出问题的确切原因。这是我的代码；

public class SelectTopSum {
    public static void main(String[] args){
        int[] arr = {5,2,10,1,33};
        int target=33;

        System.out.println(Arrays.toString(selectTop(arr, target)));
    }

    private static int[] selectTop(int[] arr, int sum) {
        //get max heap
        PriorityQueue<Integer> pq = new PriorityQueue<>(10, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);
            }
        });
        int runningTot=0;

        for (int i : arr) {
            if (runningTot<sum) {
                runningTot+=i;
                pq.add(i);
            }
            else if (i > pq.peek()) {
                runningTot-=pq.remove();
                runningTot+=i;
                pq.add(i);
            }
            while (runningTot-pq.peek()>=sum) {
                runningTot-=pq.remove();
            }
        }

        //System.out.println("priority queue is "+ pq);

        int[] result=new int[pq.size()];
        int i=0;
        while (!pq.isEmpty()) {
            result[i]=pq.remove();
            i++;
        }
        return result;
    }
}
4

1 回答 1

2

你的比较是错误的方法。

PriorityQueue将最小的项目（基于您的比较）放在第一位，并且通过说return o2.compareTo(o1);，您会将最大的整数视为最小的，但是您需要最小的元素需要放在第一位，而不是最大的。

您需要将其更改为：

return o1.compareTo(o2);

（请注意，我交换了o1and o2）

或者，为了它的价值，您可以从构造函数中完全删除第二个参数，因为它将使用Integer.compareTo，这将做您想要的。

于 2014-02-19T23:23:58.540 回答