我想找到给定正整数数组中元素的最大数目,使得它们的和小于或等于给定的k。例如,我有一个数组
[3,4,7,2,6,5,1] and k=6;
答案是3,因为1,2,3是求和6的最大元素。
int maxIceCream(vector<int>& costs, int coins) {
sort(costs.begin(), costs.end());
int ret = 0;
for (auto p : costs) if (coins >= p) {
coins -= p;
ret++;
}
return ret;
}
一种更“快捷”的方式可能是:
var maxSum = 6
var newSum = 0
let maxElements = [3,4,7,2,6,5,1].sort().filter() {
if $0 + newSum <= maxSum {
newSum += $0
return true
}
return false
} .count //returns 3
对数组进行排序,计算元素的个数,然后开始顺序对元素求和,直到它们的总和大于k,或者已经遍历了每个元素,如果总和大于k,则从计数中减去1
伪代码:
let k=6
sort the array
[1,2,3,4,5,6,7]
let sum=0
let count=7 //(7 elements in the array)
for (i=0;i<7;i++) {
sum+=array[i];
if (sum>k)
break;
}
if (sum>k)
i--;
i
是最大元素数。
给定一个有N个整数的数组A,我们需要找到子数组的最高和,使得每个元素小于或等于给定的整数X 示例:设 N=8 且数组为 [3 2 2 3 1 1 1 3] 。现在,如果 x=2,那么如果我们考虑 1 个基本索引,则通过求和 A[2] A[3] 来回答 4。如何在 O(N) 或 O(N*logN) 中执行此问题 目前,我通过检查每个可能的子阵列来采用O(N^2)方法。如何降低复杂性?
我知道一个O(n2)soln,它能以更好的方式实现吗,因为数组中元素的数量限制非常大
我需要找到总和大于或等于< code>k的最小子阵列长度。数组将只有正数。 例如 输入:< code>target = 7,< code>nums = [2,3,1,2,4,3]输出:2说明:子数组[4,3]在问题约束下长度最小。 在我的代码中,对于输入:< code>target = 7,< code>nums = [2,3,1,2,4,3]我得到的答案是< code>3,但正确答案是< cod
给定一个2D数组和一个数字。 问题:我们有一个矩阵,矩阵的每个单元格表示遍历该单元格的成本。我们从左上角开始,我们必须到达最后一个单元格(右下角)。我必须编写一个函数,返回到达而不超过的最大代价路径的代价。 如果找不到最大和小于或等于的路径,则返回,矩阵的值不能为负 解决方案:我尝试了很多代码,但没有一个返回我期望的结果。 我的第一个解决方案是在一个简单的数组中转换2D数组,并应用背包算法,但它不
我有2个输入 预期输出: 我无法解决它。所以,请不要问我的解决方案。请用java帮助解决。
我可以搜索eqaul到k之和的子数组中的正数,但下面的代码无法搜索数组中的负数。对于数组中的负数和正数,有没有找到给定和的子数组的算法? 例如,{10,2,-2,-20,10},在这个数组中查找sum为-10的子数组。子数组在这种情况下是{-20,10}。