java - 重新分配数组

Question

我正在尝试重新分配整数数组。 目的是:我有一个数组，让它成为 {2_000_000_000, 0}。

我需要:

1. 找到数组的最大元素。
2. 将其保存到临时变量。
3. 设置最大元素= 0。
4. 从下一个最大元素开始，在其余元素之间分配最大元素。如果到达数组末尾，我需要从头开始。

我的代码如下:

for (int i = 0; i < data.size(); i++){  //Looking for max element
    if (data.get(i) > max){             //of the array
        max = data.get(i);              //Save max element
        index = i;                      //Save the index of max element
    }
}
data.set(index, 0);              //Set max element = 0
if (index == data.size()){       //In case of end of array
    initPos = 0;                 //position is the beginning
}else {
    initPos = index + 1;         //If no the end - pos is the next
}

while (max > 0){                    //This block of code looks have
    if (initPos == data.size()){    //a small speed
        initPos = 0;
    }
    int oldVal = data.get(initPos);
    oldVal++;
    data.set(initPos, oldVal);
    max--;
    initPos++;                                 
}

所以问题是:代码 while(max > 0)... 似乎运行缓慢。

我是否需要使用不同的结构而不是 ArrayList 来加快分发过程？

Answer 1

我不会循环 max 次，而是计算分配给其他元素的数量。

例如，在伪代码中:

data = { 0, 10, 42, 5, 3 };
max = 42;  // you already calculated this, so in my example, I hardcode it.
index = 2; // same than above
data[index] = 0;

amountToDistribute = max / (data.length - 1); // 42 / 4 = 10.5, but it's floored to 10 since the division is made on integers
remaining = max % (data.length - 1); // 2 remaining

loop for i = 0 to i < data.length
{
    if (i != index) // don't add to the max index
    {
        data[i] += amountToDistribute; //adding 10
    }
}
// now let's add the 2 remaining
j = index + 1;
while (remaining-- > 0)
{
    if (j >= data.length)
    {
        j = 0; //reset the iterator to 0 if the end was reached
    }
    data[j++]++; // add 1 to data[3] on first iteration, then to data[4] on the second one. It increases j too once added
}
print(data); // { 10, 20, 0, 16, 14 }

在我的示例中，您有 42 个要重新分配给其他 4 个元素。

你不能将 10.5 重新分配给每个(我猜你必须只使用整数)

然后您将至少为每个元素重新分配 10(10.5 的底数是 10，因为除法是对整数进行的)。

做 42 模 4，写成 42 % 4 得到除法 42/4 的其余部分，即 2。剩下的 2 以与您相同的方式重新分配编写了您的第一个算法。

这可以被调整，所以一切都将在 1 个循环中完成。但它实际上进行了 7 次迭代(第一个循环中有 5 次，然后第二个循环中有 2 次)而不是 42 次。

在该示例中，如果将 { 0, 10, 42, 5, 3 } 替换为 { 0, 10, 4000000000(40 亿), 5, 3 } 它会在 5 次迭代中产生相同的结果(每个元素增加 10 亿，但最多增加一个)而不是你算法中的 40 亿