gpt4 book ai didi

java - 给定一个输入数组和求和,返回求和所需的最少元素

转载 作者:塔克拉玛干 更新时间:2023-11-02 19:25:38 26 4
gpt4 key购买 nike

问题是选择算法的一种变体,它选择总和至少为某个值 N 的最少数量的项目。例如,您可能想要一个总和为 5,000 的项目列表或更多,但您不想要比从输入列表中获取的项目更多的项目。因此,如果一个数字是 5,001,那么您的输出列表将包含一个数字。

另一个例子:输入列表 {3,4,5,1,2} target = {8}。输出列表将是:{5,3}

此问题已被证明可以在 excellent series of posts 中使用 binaryHeap 解决;但是当我用 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;
}
}

最佳答案

你的比较是错误的。

PriorityQueue最小项(根据您的比较)放在第一位,然后通过说return o2.compareTo(o1);,您将对待最大的整数作为最小的整数,但你需要最小的元素需要放在第一位,而不是最大的。

您需要将其更改为:

return o1.compareTo(o2);

(注意我调换了 o1o2)

或者,为了它的值(value),您可以从构造函数中完全删除第二个参数,因为它将使用 Integer.compareTo,这将执行您想要的操作。

关于java - 给定一个输入数组和求和,返回求和所需的最少元素,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21894466/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com