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

配列全体を並べ替えてから、すべてのサブ配列の合計を見つけることで問題は解決しますが、コストがかかります：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 に答える
0

以下のようにこれを実現できます: 以下のように 2 つのネストされたループを使用して、異なる数値の合計を計算します。

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 に答える