C++程序 将所有零移动到数组末尾

C++程序 将所有零移动到数组末尾

给定一个随机数的数组,在给定数组中将所有0的项推到数组的末尾。例如,如果给定的数组是{1,9,8,4,0,0,2,7,0,6,0},则应更改为{1,9,8,4,2,7,6,0,0,0,0}。所有其他元素的顺序应保持不变。预计的时间复杂度为O(n),额外空间为O(1)。

例如:

输入:  arr[] = {1, 2, 0, 4, 3, 0, 5, 0};
输出: arr[] = {1, 2, 4, 3, 5, 0, 0};

输入: arr[]  = {1, 2, 0, 0, 0, 3, 6};
输出: arr[] = {1, 2, 3, 6, 0, 0, 0};

可以有很多方法来解决这个问题。以下是解决此问题的一种简单有趣的方法。

从左到右遍历给定的数组‘arr’。在遍历时,维护数组中非零元素的计数。让计数为‘count’。对于每个非零元素arr[i],将元素放在‘arr[count]’的位置,并增加‘count’。遍历完成后,所有非零元素已经被移至前面,并将‘count’设置为第一个0的索引。现在,我们所需要做的就是运行一个循环,将所有元素从‘count’到数组的末尾变为零。

以下是上述方法的实现。

// 一个将所有零移动到数组末尾的C++程序
#include <iostream>
using namespace std;
 
// 将所有零推到数组的末尾的函数
void pushZerosToEnd(int arr[], int n)
{
    int count = 0;  // 数组中非零元素的计数
 
    // 遍历数组。如果遇到的元素是非零,则将索引“count”的元素替换为此元素
    for (int i = 0; i < n; i++)
        if (arr[i] != 0)
            arr[count++] = arr[i]; // 这里增加了计数
 
    // 现在,所有非零元素已经被移至前面,并将‘count’设置为第一个0的索引。
    // 让所有元素从count到末尾变为零。
    while (count < n)
        arr[count++] = 0;
}
 
// 测试上述函数的驱动程序
int main()
{
    int arr[] = {1, 9, 8, 4, 0, 0, 2, 7, 0, 6, 0, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    pushZerosToEnd(arr, n);
    cout << "压缩数组后的数组:\n";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    return 0;
}  

输出:

压缩数组后的数组:
1 9 8 4 2 7 6 9 0 0 0 0

时间复杂度: ** O(n),其中n是输入数组中元素的数量。

辅助空间: O(1)

其他方法:

假设开始元素为枢轴,当遍历数组时,如果遇到非零元素,则将该元素与枢轴交换,并增加索引。这将继续进行,直到所有非零元素放在左侧,所有零放在右侧。

#include <iostream>
using namespace std;
 
void swap(int A[], int i, int j)
{
    int temp = A[i];
    A[i] = A[j];
    A[j] = temp;
}
 
// 将数组中所有的 0 移动到数组的末尾
void fun(int A[], int n)
{
    int j = 0;
 
    // 当我们遇到一个非零元素时,将 `j` 递增, 然后将该元素放置在枢轴之前。
    for (int i = 0; i < n; i++) {
        if (A[i] != 0) // 枢轴为 0
        {
            swap(A, i, j);
            j++;
        }
    }
}
 
int main()
{
    int A[] = { 1, 0, 2, 0, 3, 0, 4, 0, 5, 0 };
    int n = sizeof(A) / sizeof(A[0]);
 
    fun(A, n);
 
    for (int i = 0; i < n; i++) {
        printf("%d ", A[i]);
    }
 
    return 0;
}  

输出

1 2 3 4 5 0 0 0 0 0 

时间复杂度 : O(n) ,其中 n 是输入数组中的元素数。

辅助空间 : O(1)

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程

C++ 示例