Given an array of size N I need to find the min number of values that will sum up within a min and max range.
给定一个大小为N的数组，我需要找到在最小和最大范围内求和的值的最小数量。
E.g.: consider an array[ 1,2,3,4,5 ]. I need to find min number of values from this array whose sum is greater than 5 and less than 8. Ans: since 1+5 is greater than 5 and less than 8 so the min number of values is 2 hence the answer.
例如:考虑一个数组[1,2,3,4,5]。我需要从这个数组中找到最小值，它的和大于5，小于8。答:因为1+5大于5，小于8，所以最小值数是2，所以答案是。
And below is my function which implements the logic.
下面是实现逻辑的函数。
int void CheckValue()
{
for (i = 0; i <5; i++)
if (a[i] > min && a[i] < max)
return 1;
for (i = 0; i< 4; i++)
for (j = i + 1; j < 5; j++)
if (a[i] + a[j] > min && a[i] + a[j] < max)
return 2;
for (i = 0; i < 3; i++)
for (j = i + 1; j < 4; j++)
for (k = j+1; k < 5; k++)
if (a[i] + a[j] + a[k] > min && a[i] + a[j] + a[k] < max)
return 3;
for (i = 0; i < 2; i++)
for (j = i + 1; j< 3; j++)
for (k = j + 1; k< 4; k++)
for (l = k + 1; l < 5; l++)
if (a[i] + a[j] + a[k] + a[l] > min && a[i] + a[j] + a[k] + a[l] < max)
return 4;
if(a[0]+a[1]+a[2]+a[3]+a[4]>min && a[0]+a[1]+a[2]+a[3]+a[4]<max)
return 5;
return 0;
}
It works fine but the problem is its complexity. Can anyone provide any suggestions to optimize this code further or provide a better logic to implement this.
它工作得很好，但问题在于它的复杂性。任何人都可以提供任何建议来进一步优化这段代码，或者提供更好的逻辑来实现它。
5 个解决方案
#1
1
I would propose the following solution:
我将提出以下解决办法:
Lets say the minimum value of range is minVal and maximum value is maxVal. Now sort the array.Lets say the length of array is len Do a binary search for number in array which is just <= maxVal.
设范围的最小值为minVal，最大值为maxVal。现在数组进行排序。假设数组的长度是len对数组中的数字进行二进搜索，也就是<= maxVal。
Search pass: I mean if number is at index i then number at index i+1 should be >=maxVal. Lets say the index of this number is currIndex. If this number is equal to maxVal then do binary search between 0 to currIndex for number
Search pass:我的意思是如果number在索引I处，那么索引I +1处的number应该是>=maxVal。假设这个数字的索引是currIndex。如果这个数等于maxVal，那么在0到currIndex之间进行二进制搜索
minVal and
minVal和
Search Fail: This mean highest number is array is less than the maxVal. So for this case follow the steps below: 1) Add the largest number in array to the result set. 2)Now start loop from len-1 t0 1. if arr[len-1] + arr[len] is less that maxVal then add arr[len-1] to result set and continue the loop. If arr[len-1] + arr[len] > maxVal then skip and check for arr[len-1] + arr[len].
搜索失败:这个平均值最高的数是数组小于maxVal。因此，对于这种情况，遵循以下步骤:1)将数组中最大的数字添加到结果集中。2)现在从len1 - t0 1开始循环。如果arr[len1] + arr[len]小于maxVal，则向结果集添加arr[len1]，并继续循环。如果arr[len1] + arr[len] > maxVal，则跳过并检查arr[len1] + arr[len]。
and so on.
等等。
#2
1
I don't have any experience with this kind of things so it is probable that there are better ways of doing it, but I do have some insights that may be helpful.
我对这类事情没有任何经验，所以很可能有更好的方法，但我确实有一些有用的见解。
Currently you are calculating every possible combination, you should be able to alter your algorithm to make it so that you can eliminate some combinations without having to calculate them.
目前你正在计算每一个可能的组合，你应该能够改变你的算法使它，这样你就可以消除一些组合而不需要计算它们。
I would sort the array to begin with, that will let you eliminate some values without calculating them.
我首先要对数组进行排序，这样就可以在不计算值的情况下消除某些值。
For instance if you have an array that looks like [1,2,4,5,9] and the min=11 and max=14 then your algorithm will check 1+2,1+4,1+5,1+9 then 2+4, 2+5, 2+9, 4+5, 4+9 before coming to an answer.
例如，如果你有一个看起来像[1,2,4,5,9]的数组，min=11, max=14那么你的算法会检查1+2,1+4,1+5,1+ 5，然后2+4,2+5,2+9,4+5,4+5,4+9，然后得出答案。
If instead you start with the highest number first you can eliminate all possible 1 combinations by doing the calculation 9+1, since 9+1<=11 it must be the case that all other possible 1 combinations are invalid for the two number sum, the same with all possible 2 combinations. If you add logic like this to your code you should have less superfluous calculations, hopefully speeding your code up.
如果你从最高的数字开始，你可以通过计算9+1来消除所有可能的1个组合，因为9+1<=11，那么所有其他可能的1个组合对于两个数字和都是无效的，对所有可能的2个组合也是如此。如果您将这样的逻辑添加到代码中，那么就应该减少不必要的计算，希望能加快代码的速度。
#3
1
Is this a homework question?
这是家庭作业吗?
Your question is really not clear but here is what i would :
你的问题确实不清楚，但我想说的是:
Sort it. nlogn.
Start with adding the first element and last element. Is that in the range? Take the first pointer from one end, lets say from beginning, move it to middle and add the middle number and the last number, first pointer + last pointer. is that in the range? you can move the first pointer to the middle between first and last pointer, ie: right by 3/4 of the sequence.
排序。nlogn。首先添加第一个元素和最后一个元素。在这个范围内吗?从一端取第一个指针，假设从开始，移动到中间，添加中间数字和最后一个数字，第一个指针+最后一个指针。在这个范围内吗?你可以把第一个指针移到第一个和最后一个指针之间的中间，也就是说:在序列的3/4处。
So you are using binary search here with two pointers on a sorted sequence.
所以你在这里使用二进制搜索，在排序序列上有两个指针。
This will give you an estimate number of elements, which will be in range. I hope you got the idea.
这将给你一个元素的估计值，它将在范围内。我希望你有这个想法。
You can move the second pointer to middle, if your sum is out of range.
你可以把第二个指针移到中间，如果你的和超出了范围。
This will give you nlogn.
这会给你nlogn。
Please note that this is just for two numbers, i m not sure if you are asking for all possible numbers whose addition would be in the range or only two numbers?
请注意，这只是两个数字，我不确定你是否要求所有可能的数字，它们的加法都在范围内还是只有两个数字?
two numbers is easy, nlogn does it
两个数很简单，nlogn可以
All possible subset is subset sum problem which is np hard. exponential which is 2**n.
所有可能的子集都是属于np困难的子集和问题。2 * * n指数。
#4
0
I think you should consider sorting your array, there are many efficient algoritms for this.
我认为你应该考虑排序你的数组，有很多有效的算法。
Then start from the biggest value and cummulatively add smaller values in sorted order, checking the condition at each step.
然后从最大的值开始，并在排序的顺序中添加较小的值，检查每个步骤的条件。
#5
0
This is a rather complex problem, likely to be np hard.
这是一个相当复杂的问题，可能是np困难。
One thing that comes to mind is that it slightly resembles the 'knapsack problem'. Perhaps you can find an implementation of that and adapt it.
我想到的一件事是，它有点像“背包问题”。也许您可以找到实现并对其进行修改。
If the minimum amount of items is expected to be small, you can of course use a brute force approach:
如果最小数量的物品被期望是小的，你当然可以使用蛮力方法:
- Set minVal = 1
- 设置minVal = 1
- Find all sets of size minVal
- 查找所有大小的minVal。
- As long as none of the sets meet your criteria, add 1 to minVal and go to step 2
- 只要没有一组满足您的标准，将1添加到minVal中并进入步骤2
#1
1
I would propose the following solution:
我将提出以下解决办法:
Lets say the minimum value of range is minVal and maximum value is maxVal. Now sort the array.Lets say the length of array is len Do a binary search for number in array which is just <= maxVal.
设范围的最小值为minVal，最大值为maxVal。现在数组进行排序。假设数组的长度是len对数组中的数字进行二进搜索，也就是<= maxVal。
Search pass: I mean if number is at index i then number at index i+1 should be >=maxVal. Lets say the index of this number is currIndex. If this number is equal to maxVal then do binary search between 0 to currIndex for number
Search pass:我的意思是如果number在索引I处，那么索引I +1处的number应该是>=maxVal。假设这个数字的索引是currIndex。如果这个数等于maxVal，那么在0到currIndex之间进行二进制搜索
minVal and
minVal和
Search Fail: This mean highest number is array is less than the maxVal. So for this case follow the steps below: 1) Add the largest number in array to the result set. 2)Now start loop from len-1 t0 1. if arr[len-1] + arr[len] is less that maxVal then add arr[len-1] to result set and continue the loop. If arr[len-1] + arr[len] > maxVal then skip and check for arr[len-1] + arr[len].
搜索失败:这个平均值最高的数是数组小于maxVal。因此，对于这种情况，遵循以下步骤:1)将数组中最大的数字添加到结果集中。2)现在从len1 - t0 1开始循环。如果arr[len1] + arr[len]小于maxVal，则向结果集添加arr[len1]，并继续循环。如果arr[len1] + arr[len] > maxVal，则跳过并检查arr[len1] + arr[len]。
and so on.
等等。
#2
1
I don't have any experience with this kind of things so it is probable that there are better ways of doing it, but I do have some insights that may be helpful.
我对这类事情没有任何经验，所以很可能有更好的方法，但我确实有一些有用的见解。
Currently you are calculating every possible combination, you should be able to alter your algorithm to make it so that you can eliminate some combinations without having to calculate them.
目前你正在计算每一个可能的组合，你应该能够改变你的算法使它，这样你就可以消除一些组合而不需要计算它们。
I would sort the array to begin with, that will let you eliminate some values without calculating them.
我首先要对数组进行排序，这样就可以在不计算值的情况下消除某些值。
For instance if you have an array that looks like [1,2,4,5,9] and the min=11 and max=14 then your algorithm will check 1+2,1+4,1+5,1+9 then 2+4, 2+5, 2+9, 4+5, 4+9 before coming to an answer.
例如，如果你有一个看起来像[1,2,4,5,9]的数组，min=11, max=14那么你的算法会检查1+2,1+4,1+5,1+ 5，然后2+4,2+5,2+9,4+5,4+5,4+9，然后得出答案。
If instead you start with the highest number first you can eliminate all possible 1 combinations by doing the calculation 9+1, since 9+1<=11 it must be the case that all other possible 1 combinations are invalid for the two number sum, the same with all possible 2 combinations. If you add logic like this to your code you should have less superfluous calculations, hopefully speeding your code up.
如果你从最高的数字开始，你可以通过计算9+1来消除所有可能的1个组合，因为9+1<=11，那么所有其他可能的1个组合对于两个数字和都是无效的，对所有可能的2个组合也是如此。如果您将这样的逻辑添加到代码中，那么就应该减少不必要的计算，希望能加快代码的速度。
#3
1
Is this a homework question?
这是家庭作业吗?
Your question is really not clear but here is what i would :
你的问题确实不清楚，但我想说的是:
Sort it. nlogn.
Start with adding the first element and last element. Is that in the range? Take the first pointer from one end, lets say from beginning, move it to middle and add the middle number and the last number, first pointer + last pointer. is that in the range? you can move the first pointer to the middle between first and last pointer, ie: right by 3/4 of the sequence.
排序。nlogn。首先添加第一个元素和最后一个元素。在这个范围内吗?从一端取第一个指针，假设从开始，移动到中间，添加中间数字和最后一个数字，第一个指针+最后一个指针。在这个范围内吗?你可以把第一个指针移到第一个和最后一个指针之间的中间，也就是说:在序列的3/4处。
So you are using binary search here with two pointers on a sorted sequence.
所以你在这里使用二进制搜索，在排序序列上有两个指针。
This will give you an estimate number of elements, which will be in range. I hope you got the idea.
这将给你一个元素的估计值，它将在范围内。我希望你有这个想法。
You can move the second pointer to middle, if your sum is out of range.
你可以把第二个指针移到中间，如果你的和超出了范围。
This will give you nlogn.
这会给你nlogn。
Please note that this is just for two numbers, i m not sure if you are asking for all possible numbers whose addition would be in the range or only two numbers?
请注意，这只是两个数字，我不确定你是否要求所有可能的数字，它们的加法都在范围内还是只有两个数字?
two numbers is easy, nlogn does it
两个数很简单，nlogn可以
All possible subset is subset sum problem which is np hard. exponential which is 2**n.
所有可能的子集都是属于np困难的子集和问题。2 * * n指数。
#4
0
I think you should consider sorting your array, there are many efficient algoritms for this.
我认为你应该考虑排序你的数组，有很多有效的算法。
Then start from the biggest value and cummulatively add smaller values in sorted order, checking the condition at each step.
然后从最大的值开始，并在排序的顺序中添加较小的值，检查每个步骤的条件。
#5
0
This is a rather complex problem, likely to be np hard.
这是一个相当复杂的问题，可能是np困难。
One thing that comes to mind is that it slightly resembles the 'knapsack problem'. Perhaps you can find an implementation of that and adapt it.
我想到的一件事是，它有点像“背包问题”。也许您可以找到实现并对其进行修改。
If the minimum amount of items is expected to be small, you can of course use a brute force approach:
如果最小数量的物品被期望是小的，你当然可以使用蛮力方法:
- Set minVal = 1
- 设置minVal = 1
- Find all sets of size minVal
- 查找所有大小的minVal。
- As long as none of the sets meet your criteria, add 1 to minVal and go to step 2
- 只要没有一组满足您的标准，将1添加到minVal中并进入步骤2