将数组通过将值移位到相邻元素来转换为另一个数组

Question

我有两个数组，输入数组和输出数组。目标是通过对给定步骤内的相邻元素执行1个值的移位来将输入数组转换为输出数组。例如：输入数组为[0,0,8,0,0]，输出数组为[2,0,4,0,2]。这里第一步将是[0,1,7,0,0]，第二步将是[0,1,6,1,0]等等。

如何高效地实现此算法？我考虑使用BFS，但是我们必须从每个元素开始进行BFS，这可能是指数级的。有人能提出解决此问题的方案吗？

- user4090410

Answer 1

我认为你可以通过在每个方向上扫描来追踪当前数组和期望输出数组中的累积值，并根据需要将值向前推移，从而简单地完成此操作：

scan from the left looking for first cell where
  cumulative value > cumulative value in desired output
while that holds move 1 from that cell to the next cell to the right 

scan from the right looking for first cell where
  cumulative value > cumulative value in desired output
while that holds move 1 from that cell to the next cell to the left 

针对您的示例，步骤如下：

FWD： [0,0,8,0,0] [0,0,7,1,0] [0,0,6,2,0] [0,0,6,1,1] [0,0,6,0,2]

REV： [0,1,5,0,2] [0,2,4,0,2] [1,1,4,0,2] [2,0,4,0,2]

- Ian Mercer

Answer 2

我认为BFS可能会起作用。

请注意，n*O(n+m) = O(n^2+nm)，因此不是指数级的。

此外，您可以使用Floyd-Warshall算法和Johnson算法，在“平坦”图形的情况下，将权重设为1，甚至按实际距离连接顶点，并且可能节省一些迭代次数。

希望这有所帮助 :)

- yd1

Answer 3

一个简单的贪心算法就可以解决问题，并且使用最少的步骤完成任务。该函数返回完成任务所需的总步数。

int shift(std::vector<int>& a,std::vector<int>& b){

    int n = a.size();

    int sum1=0,sum2=0;
    for (int i = 0; i < n; ++i){
        sum1+=a[i];
        sum2+=b[i];
    }

    if (sum1!=sum2)
    {
        return -1;
    }

    int operations=0;
    int j=0;
    for (int i = 0; i < n;)
    {
        if (a[i]<b[i])
        {
            while(j<n and a[j]==0){
                j++;
            }
            if(a[j]<b[i]-a[i]){
                operations+=(j-i)*a[j];
                a[i]+=a[j];
                a[j]=0;
            }else{
                operations+=(j-i)*(b[i]-a[i]);
                a[j]-=(b[i]-a[i]);
                a[i]=b[i];
            }
        }else if (a[i]>b[i])
        {
            a[i+1]+=(a[i]-b[i]);
            operations+=(a[i]-b[i]);
            a[i]=b[i];
        }else{
            i++;
        }
    }

    return operations;
}

这里-1是一个特殊值，表示给定的数组无法转换为所需的数组。

时间复杂度：O(n)。

- v78

---

这会将值移动超过一个步骤，不是吗？（当 j > i + 1 时） - Ian Mercer

在你的代码中，什么构成了一个单独的“步骤”？每次“shift”的调用是否执行一个步骤，还是所有工作都在一次调用中完成？因为看起来它似乎可以在一次调用中执行多个更改...“操作”的意义是什么，返回值的语义是什么？-1是一个特殊值吗？ - yeoman

Answer 4

void transform(int[] in, int[] out, int size)
{
    int[] state = in.clone();

    report(state);

    while (true)
    {
        int minPressure = 0;
        int indexOfMinPressure = 0;

        int maxPressure = 0;
        int indexOfMaxPressure = 0;

        int pressureSum = 0;

        for (int index = 0; index < size - 1; ++index)
        {
            int lhsDiff = state[index] - out[index];
            int rhsDiff = state[index + 1] - out[index + 1];

            int pressure = lhsDiff - rhsDiff;

            if (pressure < minPressure)
            {
                minPressure = pressure;
                indexOfMinPressure = index;
            }

            if (pressure > maxPressure)
            {
                maxPressure = pressure;
                indexOfMaxPressure = index;
            }

            pressureSum += pressure;
        }

        if (minPressure == 0 && maxPressure == 0)
        {
            break;
        }

        boolean shiftLeft;

        if (Math.abs(minPressure) > Math.abs(maxPressure))
        {
            shiftLeft = true;
        }
        else if (Math.abs(minPressure) < Math.abs(maxPressure))
        {
            shiftLeft = false;
        }
        else
        {
            shiftLeft = (pressureSum < 0);
        }

        if (shiftLeft)
        {
            ++state[indexOfMinPressure];
            --state[indexOfMinPressure + 1];
        }
        else
        {
            --state[indexOfMaxPressure];
            ++state[indexOfMaxPressure + 1];
        }

        report(state);
    }
}

- yeoman