C++程序 将所有0移动到数组末尾(使用单次遍历)

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)。

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程

C++ 示例