-3

n>=0を指定して、パターンを使用して配列を作成します{1,1, 2,1, 2, 3, ... 1, 2, 3 .. n}。

例として、を指定した場合n=3、メソッドは配列をとして返す必要があります{1,1,2,1,2,3}。

私の解決策はここにあります...

public int[] upSeries(int n) {

    int var1 = n + 1;        
    int var2 = n;
    int var3 = (var1*var2) / 2;
    int arr_length = var3;
    int value = 1;
    int index = 0;
    int[] arr = new int[arr_length];
    for (int j = 0; j < arr.length; j++) {
        for (int p = 0; p < j + 1; p++) {
            arr[index] = value;
            value++;

            if (index == arr.length - 1) {
                arr[index] = n;
                break;
            } else {
                index++;
            }
        }
        value = 1;
    }
    return arr;
}

最善の解決策は何ですか？

4

6 に答える 6

2

少しきれいにしました。しかし、それは同じ一般的な考え方です。削除できる冗長性がいくつかありました。

public int[] upSeries(int i) {
    assert i >= 0;        

    int[] array = new int[(i * (i+1)) / 2)];  // Standard Sum
    int seriesnum = 1;
    int seriesmax= 1;
    for (int index=0; index < array.length; index++) {
        array[index] = seriesnum;            

        if (seriesnum++ == seriesmax) {
            seriesnum = 1;
            seriesmax++;
        }
    }

    return array;
}

この解は、一定の倍数だけ優れています。Big-Oh を探している場合は、どちらも O(i^2) であり、これ以上のことはできません。

改善できない理由の証明が必要な場合。最初に、返される配列のサイズが ((i) * (i+1)) /2) であることを証明します。次に、配列内のすべての位置を埋めなければならないという議論をします。O(i^2) よりも優れている場合は、配列内のすべての位置を埋めていません。

于 2012-12-07T18:05:28.227 に答える
1

整数演算が原因で、偶数入力に対してコードが失敗します。

@RohitJain が示した例では、 を実行しますが(4+1)/2、これは誤って 2 を与えています。考えられる解決策は、最初に を乗算i*(i+1)し、後で 2 で除算することです。

パフォーマンスについて:
出力と比較して線形時間で実行しています-要素ごとに1回の反復では、実行できる深刻なことは何もありません。おそらく、いくつかのローカルマイクロ最適化のみです。

編集：

新しいコードにも問題があります - 奇妙なエッジケースn== 46341で、配列サイズは 1073720970 である必要があり、これは (AFAIK) 理論的には可能です。
ただし、46341*46342 を乗算すると範囲外になり、整数オーバーフローと負のサイズの配列が発生します。

これは、このケースを手動で確認することで解決できます。

于 2012-12-07T18:06:06.137 に答える
0

ルチ、あなたのループにはO(n^2)時間がかかります-より正確には、それは正確に(n)(n+1)/2時間がかかります。ただし、これはアレイのサイズでもあるため、これ以上のことはできません。

于 2012-12-07T18:03:31.700 に答える
0

ループは問題ありません。このタイプのリストを作成する効率には制限がありますが、コードを少しクリーンアップできます。var1は役に立たず、が奇数のvar2場合にのみ有用であり (それ以外の場合は不正確です)、まったく機能しません。配列の長さは、1 から∑<code>i またはの合計になります。その合計を配列宣言の中に入れることもできるので、簡単に理解できます。ivar3iint arr_length = i*(i+1)/2

于 2012-12-07T18:05:57.697 に答える
0

これはどう。

public static void main(String args[]) {

    int n =3;
    StringBuilder sb = new StringBuilder();
    String prei = "";
    for(int i=1;i<n+1;i++){
        prei    =prei + sb.append(i).toString();
    }

     char [] myArr = prei.toCharArray();
    }
}
于 2012-12-07T18:25:58.097 に答える
0 
List<Integer> myarrayList=new ArrayList<Integer>();
public void show(int n){
for(int i=1;i<n+1;i++){
    if(n==1){
        myarrayList.add(n);
        break;
    }
    if(n>1){
        for(int j=1;j<i+1;j++){
            myarrayList.add(j);
        }
    }

}
}

public  int[] convertIntegers(List<Integer> integers)
{
int[] ret = new int[integers.size()];
Iterator<Integer> iterator = integers.iterator();
for (int i = 0; i < ret.length; i++)
{
    ret[i] = iterator.next().intValue();
}
return ret;
}
}

最初に show 関数を呼び出し、次に convertIntegers を呼び出します。

于 2012-12-07T18:27:05.983 に答える