移位n次算法

Question

给定一个数组，从数组的开头到结尾，每当遇到数字“2”时，就在它后面添加另一个“2”。
这样做时，数组中的最后一个元素将被删除，因为最终数组的大小应与初始数组的大小相同。

例如，如果初始数组是

[23, 2, 3, 12, 2, 2, 34, 55, 66, 79]

那么修改后的数组应该是

[23, 2, 2, 3, 12, 2, 2, 2, 2, 34]

预期时间复杂度为 O(n)，您应该原地进行（仅使用恒定数量的额外内存）。

在 O(n^2) 中很容易，但在 O(n) 中 ???

Answer 1

遍历数组两次

迭代计算您找到了多少个 2，并跟踪最终数组的大小，以便您知道何时停止。在您的示例中，当您到达 34 时，您应该知道最后三个元素无关紧要，因为在此之前您已经看到了三个 2。记住你停在哪里。
从您在第一遍停止的地方向后遍历数组。将每个元素复制到数组的末尾。如果是2，复制两次。

有一个极端情况需要处理，即最后一个适合的元素是 2 但没有空间容纳它的副本。您必须在两次传递中都考虑到这一点。

Answer 2

    #include<bits/stdc++.h>
using namespace std;



int main()
{
    int arr[]={23, 2, 3, 12, 2, 2, 2, 55, 66, 79};
    int size=sizeof(arr)/sizeof(arr[0]);
    int p=size;
    int sd=size-1;
    for(int i=0;i<p;i++){
        if(arr[i]==2 && i!=p-1)
        p--;
    }
    int i=p-1;
    while(i>=0){
        if(arr[i]!=2){
            arr[sd]=arr[i];
            sd--;i--;
        }
        else if(arr[i]==2 && i==p-1){
            arr[sd]=arr[i];
            sd--;i--;
        }
        else{
            arr[sd]=arr[i];
            sd--;i--;
            arr[sd]=2;sd--;
        }
    }
for(int i=0;i<size;i++){
       
       cout<<arr[i]<<endl;
    }
return 0;

}

移位n次算法

Shifting n times algorithm

algorithm

complexity-theory