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)