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

在C++中，我们经常需要处理数组。有些情况下，我们需要将数组中的所有零移动到数组末尾。这个问题看起来简单，但实际上有很多方法可以解决它。在本文中，我们将介绍三种不同的解决方案。

方法一：暴力移动

最简单的方法是使用暴力解决方案，即遍历整个数组，将所有零移动到数组的末尾。以下是这个算法的C++代码实现：

void moveZeroes(vector<int>& nums) {
    int count = 0; // count表示所有已经遍历到的数字中0的个数
    for (int i = 0; i < nums.size(); i++) {
        if (nums[i] == 0) {
            count++;
        } else {
            nums[i - count] = nums[i];
        }
    }
    for (int i = nums.size() - count; i < nums.size(); i++) {
        nums[i] = 0;
    }
}

该函数接受一个整数向量nums作为参数，并通过引用修改它。我们在遍历整个数组时记录了所有遇到的零的数量。然后，我们将非零数字向前移动，并在数组末尾添加适当数量的零。

我们可以用以下代码测试它：

vector<int> nums{1, 0, 3, 0, 5, 0, 7, 0, 9};

moveZeroes(nums);

for (int num : nums) {
    cout << num << " ";
}

输出应该是：1 3 5 7 9 0 0 0 0

方法二：双指针

第二种解决方案是使用双指针。我们使用两个指针，一个指向最左侧的零元素，另一个指向当前元素。每当我们遇到一个非零元素时，我们将其复制到左指针位置，并将左指针向右移动。以下是该算法的C++代码实现：

void moveZeroes(vector<int>& nums) {
    int left = 0;
    for (int right = 0; right < nums.size(); right++) {
        if (nums[right] != 0) {
            nums[left++] = nums[right];
        }
    }
    for (int i = left; i < nums.size(); i++) {
        nums[i] = 0;
    }
}

这个函数的C++代码与前面的函数类似。只不过我们用两个指针循环遍历整个数组。右指针表示当前元素，而左指针表示最左侧的零元素。

以下是用C ++代码实现的测试代码：

vector<int> nums{1, 0, 3, 0, 5, 0, 7, 0, 9};

moveZeroes(nums);

for (int num : nums) {
    cout << num << " ";
}

输出应该是：1 3 5 7 9 0 0 0 0

方法三：快速排序

第三种解决方案是使用快速排序算法。在快速排序算法中，我们使用一个“支点”（pivot）元素将数组分为两个部分。在此特定情况下，我们将零视为支点元素。一旦支点确定，我们就可以在数组中找到第一个非零元素。然后，我们将非零元素交换到数组的左侧，并递归地重复此过程。以下是实现QuickSort的C++代码：

void quickSort(vector<int>& nums, int left, int right) {
    int i = left;
    int j = right;
    int pivot = 0;

    while (i <= j) {
        while (nums[i] == pivot) {
            i++;
        }

        while (nums[j] != pivot) {
            j--;
        }

        if (i <= j) {
            swap(nums[i], nums[j]);
            i++;
            j--;
        }
    }

    if (left < j) {
        quickSort(nums, left, j);
    }

    if (i < right) {
        quickSort(nums, i, right);
    }
}

void moveZeroes(vector<int>& nums) {
    quickSort(nums, 0, nums.size() - 1);
}

在这里，我们首先实现了QuickSort的标准分区函数，检查左指针和右指针当前指向的元素是否满足条件。如果不满足条件，我们就交换这两个元素。然后递归地分治左侧和右侧的子数组。

以上是快速排序算法的主要功能，用于在数组中找到并移动零元素。以下是用于测试的C++代码：

vector<int> nums{1, 0, 3, 0, 5, 0, 7, 0, 9};

moveZeroes(nums);

for (int num : nums) {
    cout << num << " ";
}

输出应该是：1 3 5 7 9 0 0 0 0

结论

在本文中，我们介绍了三种方法来将所有零移动到C++数组的末尾。第一种方法是最简单的，即暴力移动。第二种方法是使用双指针。最后，我们介绍了快速排序算法，也可以解决这个问题。尽管三种方法执行速度不同，根据你的使用情况，你可以选择更适合你的方法。