题意整理。

• 给定一个数组。
• 将数组中所有0元素移到末尾，非0元素移到开头，同时保持非0元素相对位置不变。

方法一（双指针）

1.解题思路

• 定义两个指针id和i，id总是指向第一个0所在位置，i指向游标所在位置，遍历数组所有元素。
• i指向元素不为0，则交换i、id位置元素，同时id指针后移。

举例说明：对应数组[1,0,3,4,0,-3]，id本来指向1，i指针开始也指向1，由于不等于0，交换i、id位置元素，由于在同一位置，所以数组相当于没有变化，id指针后移，此时id指向0，i指向0时，不作处理，i指向3时，交换i、id位置元素，数组变为[1,3,0,4,0,-3]，同时id后移一位，仍然指向0，i指针继续遍历数组中的元素，作类似的处理，这样就会一步步将0移到数组末尾，同时，其它元素相对位置不变。

动图展示：

2.代码实现

#include <iostream>
using namespace std;

void func(int* p, int n);

int main() {

    int arr[6] = { 0 };
    for (int i = 0; i < 6; i++) {
        cin >> arr[i];
    }

    func(arr, 6);

    for (int i = 0; i < 6; i++) {
        if (i == 5) {
            cout << arr[i] << endl;
        }
        else {
            cout << arr[i] << " ";
        }
    }

    return 0;
}

void func(int* p, int n) {

    //id指向第一个0所在位置
    int id=0;
    //i指向游标所在位置，遍历数组所有元素
    for(int i=0;i<n;i++){
        if(p[i]!=0){
            int temp=p[i];
            p[i]=p[id];
            p[id++]=temp;
        }
    }


}

3.复杂度分析

• 时间复杂度：需要遍历数组中所有元素，所以时间复杂度为$O(n)O(n)$。
• 空间复杂度：需要额外常数级别的空间，所以空间复杂度为$O(1)O(1)$。