给定一个输入数组和一个目标和，返回达到目标和所需的最小元素数量。

Question

给定一个输入数组和一个目标和，返回达到目标和所需的最小元素数量。

3

问题是选择算法的一种变体，选择最少数量的项目，使其总和至少为N。例如，您可能希望拥有一个项目列表，其总和为5,000或更多，但不想从输入列表中取出更多项。因此，如果一个数字是5,001，则您的输出列表将包含单个数字。

另一个例子：输入列表{3,4,5,1,2}，目标={8}。输出列表将为：{5,3}。

这个问题已经被证明可以使用二进制堆在这个优秀的系列文章中解决；但是当我在Java中实现时，我没有得到期望的输出。我得到了整个输入列表。我无法找到问题的确切原因。这是我的代码；

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;
    }
}

- brain storm

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Bernhard Barker · Accepted Answer

你的比较方式是错误的。 PriorityQueue 根据你的比较方式，将最小的元素放在前面。但是，通过使用 return o2.compareTo(o1);，你会把最大的整数视为最小的，而实际上你需要的是最小的元素排在前面，而不是最大的。

你需要将代码改为：

return o1.compareTo(o2);

（注意我交换了 o1 和 o2）或者，仅供参考，您可以完全从构造函数中删除第二个参数，因为它将使用 Integer.compareTo，这样就可以实现您想要的功能。