时间戳

首页 > 解决方案 > 重新分配数组

java - 重新分配数组

问题描述

我正在尝试重新分配整数数组。目的是：我有一个数组，顺其自然{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 来加快分发过程？

标签： javaarraysalgorithmarraylist

解决方案

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 (4 billions), 5, 3 }会在 5 次迭代中产生相同的结果（每个元素增加 10 亿，但最大值），而不是算法中的 40 亿

推荐阅读