0

我需要通过添加不同数量的数组来获得一个我无法获得的最小数量。基本上如果我有这些数字：1,1,1,5; 我可以得到 1,2,3,5,6... 但我不能得到 4 所以这就是我要找的数字。现在这是我的代码：

import java.util.Scanner;
public class Broj_6 {

public static void main(String[] args) {
    Scanner unos = new Scanner(System.in);
    int k;
    int n = unos.nextInt();
    int niz []= new int [n];
    for(int i = 0;i<n;i++){
        niz[i]=unos.nextInt();
    }
    BubbleSort(niz);
    for(int i = 0;i<n;i++){
        System.out.print(niz[i] + " ");
    }
    for(int br = 1;br<=10000;br++){ 
        for(k = 1;k<n;k++){
            if(niz[k]>br){
                break;
            }
        }
        int podniz [] = new int [k];
        for(int i=0;i<podniz.length;i++){
            niz[i] = podniz[i];
        }
        //This is where I will need my logic to go
    }
}

static void BubbleSort (int [] niz){
    int pom;
    for(int i = 0;i<niz.length-1;i++){
        for(int j = 0;j<niz.length-1-i;j++){
            if(niz[j]>niz[j+1]){
                pom = niz[j];
                niz[j] = niz[j+1];
                niz[j+1] = pom;
            }
        }
    }
}
}

因此，代码通过单独测试从 1 到 100000 的每个数字，并创建一个包含小于数字本身的所有数字的子数组。现在这是问题所在，我不知道如何混合和匹配子数组中的数字，以便它可以获取（或不获取）所需的数字。当每个组合都被测试并且没有想要的数字时，我会打破；循环并打印 i。澄清一下，我只能用加法，每个数字只能进一次

4

2 回答 2

0

您可以按如下方式实现：使用两个嵌套循环，如下所示来计算不同数字的总和：

List<Integer> additionList = new ArrayList<Integer>();
int []inputNumbers = .... // Logic to read inputs
for(int _firstIndex = 0; _firstIndex < totalInputs; _firstIndex++){
    for(int _secondIndex = _firstIndex + 1; _secondIndex < totalInputs; _secondIndex++){
        additionList.add(inputNumbers[_firstIndex]); // only because you have 1 in the sample output
        additionList.add(inputNumbers[_firstIndex] + inputNumbers[_secondIndex ]);
    }
}

然后排序additionList并查找任何丢失的条目。第一个缺失的条目将是您的答案，

于 2013-02-27T12:50:19.937 回答
0

对整个数组进行排序，然后找到所有子数组的总和确实可以解决问题，但代价高昂：O(2n^2) ~ O(n^2)。

解决这个问题的更有效方法是 Kadane 的算法：http ://en.wikipedia.org/wiki/Maximum_subarray_problem

算法的作用：从第一个元素开始并增加数组大小（子数组），直到达到您想要的总和。

my_num = 1;
while(true){
  if(sum_subarray) > my_num){
    current position = new subarray;
}

而这个子数组的概念是通过 Kadane 的方法计算出来的：

def sum_subarray(A):
sum_ending_here = sum_so_far = 0
for x in A:
    sum_ending_here = max(0, max_ending_here + x)
    sum_so_far = max(sum_so_far, sum_ending_here)
return sum_so_far

我无法完全解决问题。这里提到的 'my_num' 需要从 1 开始递增，并在my_num > max_sum. 我希望有人可以添加它并使其可编译。

笔记：

如果数组中存在负元素，这也会引起注意。

于 2013-02-27T13:16:45.707 回答