C++程序 将所有0移动到数组末尾(使用单次遍历)
给定一个由 n 个数字组成的数组。问题是将所有0移动到数组末尾,同时保持其他元素的顺序。只需要对数组进行单次遍历。
举例:
Input : arr[] = {1, 2, 0, 0, 0, 3, 6}
Output : 1 2 3 6 0 0 0
Input: arr[] = {0, 1, 9, 8, 4, 0, 0, 2, 7, 0, 6, 0, 9}
Output: 1 9 8 4 2 7 6 9 0 0 0 0 0
算法:
moveZerosToEnd(arr, n)
初始化 count = 0
对 于 i = 0 到 n-1
如果 (arr[i] != 0) 则
交换(arr[count++], arr[i])
// 将所有0移动到数组的末尾的C++实现
#include <iostream>
using namespace std;
//将所有0移到数组的末尾的函数
void moveZerosToEnd(int arr[], int n)
{
//非零元素的数量
int count = 0;
//遍历数组。如果arr[i]是非零数,则
//交换索引“count”处的元素和索引“i”的元素
for (int i = 0; i < n; i++)
if (arr[i] != 0)
swap(arr[count++], arr[i]);
}
//打印数组元素的函数
void printArray(int arr[], int n)
{
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
}
//主程序
int main()
{
int arr[] = { 0, 1, 9, 8, 4, 0, 0, 2,
7, 0, 6, 0, 9 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "原始数组:";
printArray(arr, n);
moveZerosToEnd(arr, n);
cout << "
修改后的数组:";
printArray(arr, n);
return 0;
}
输出:
原始数组:0 1 9 8 4 0 0 2 7 0 6 0 9
修改后的数组:1 9 8 4 2 7 6 9 0 0 0 0 0
时间复杂度:O(n)。
辅助空间:O(1)。