-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。

关于性能：
与输出相比，您在线性时间内运行 - 每个元素进行一次迭代，没有什么可以做的严重的事情，也许只有一些局部微优化。

编辑：

新代码还有一个问题——一个奇怪的边缘情况n== 46341，数组大小应该是 1073720970，这在理论上是可能的（AFAIK）。
但是，当乘以 46341*46342 时，您会超出范围，这会导致整数溢出- 以及一个负大小的数组。

这可以通过手动检查这种情况来解决。

于 2012-12-07T18:06:06.137 回答
0

Ruchi，你的循环需要O(n^2)时间——更准确地说，它需要(n)(n+1)/2时间。但是，由于这也是数组的大小，因此不可能做得更好。

于 2012-12-07T18:03:31.700 回答
0

你的 for 循环很好，这种类型的列表的效率是有限的，但你的代码可以清理一下。var1有点没用，只有在奇数var2时才有用i（否则它不准确），并且var3绝对没有任何作用。数组的长度将是 1 到i或 ∑<code>i 或的总和int 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 回答