n在将其作为参数传递给函数后为0，这里似乎有什么问题?

Question

这里的问题是把所有的0放到数组的末尾。我已经写了下面的代码，但是在将(arr, n)传递给pushzero()函数后，当我试图打印数组时，它什么也不做，并且在调用pushzero()函数后，n的值变为零。

#include <bits/stdc++.h>
using namespace std;
void pushzero(int arr[], int n) {   
for (int i = 0; i < n; i++) {   
for (int j = 0; j < i + 1; j++) {
if (arr[j] == 0) {
swap(arr[j+1], arr[j]);
}
}
}
}
int main() {
int arr[] = { 2, 6, 0, 0, 1, 9, 0, 8, 0 };
int n = sizeof(arr) / sizeof(arr[0]);

for (int i = 0; i < n; i++) {
cout << arr[i] << " " << "n";
}
pushzero(arr, n);

for (int j = 0; j < n; j++) { // n is 0 here
cout << arr[j] << " ";
}
return 0;
}

Answer 1

代码有未定义的行为，因为pushzero中的内循环迭代得太远:

• 在pushzero外循环的最后一次迭代中，i的值为n - 1
• 内循环的最后一次迭代，j的值为i，因此n - 1，
• 如果测试arr[j] == 0为真，因为数组中有多个零，swap将被调用来交换arr[j]和arr[j+1]的值，因此读取和修改超出数组末尾的arr[n]。

这个未定义的行为可能会产生令人惊讶的结果，例如您观察到的行为，可能是因为n存储在堆栈内存中，就在数组arr之后，这表明您禁用了优化。

将循环测试更改为j < i修复了越界访问，但没有达到您的目标。你应该写j < n - i - 1以保证正常操作。

修改后的版本:

#include <bits/stdc++.h>
using namespace std;
void pushzero(int arr[], int n) {   
for (int i = 0; i < n; i++) {   
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] == 0) {
swap(arr[j+1], arr[j]);
}
}
}
}
int main() {
int arr[] = { 2, 6, 0, 0, 1, 9, 0, 8, 0 };
int n = sizeof(arr) / sizeof(arr[0]);

for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "n";
pushzero(arr, n);

for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "n";
return 0;
}

上面的实现是次优的，因为它有O(N²)的复杂性。下面是线性执行时间的简单示例:

void pushzero(int arr[], int n) {   
int i, j;
for (i = j = 0; i < n; i++) {   
if (arr[i] != 0) {
arr[j++] = arr[i];
}
}
while (j < n) {   
arr[j++] = 0;
}
}

或者使用swap()函数，稍微多做一些工作:

void pushzero(int arr[], int n) {  
for (int i = 0, j = 0; i < n; i++) {   
if (arr[i] != 0) {
swap(arr[i], arr[j++]);
}
}
}

您还可以使用更习惯的c++解决方案，如@PaulMcKenzie:

所建议的那样

#include <algorithm>
void pushzero(int arr[], int len) {   
std::stable_partition(arr, arr + len, [](int n) { return n != 0; });
}

Answer 2

您可以使用0作为枢轴元素，当您看到非零元素时，将其与枢轴元素交换。所以所有的非零元素都在开头

void pushzero(int arr[], int n) {  
int j =0; 
for (int i = 0; i < n; i++) {   
if(arr[i] != 0) {
swap(arr[i], arr[j]);
j++;
}
}
}

演示:https://godbolt.org/z/oMdxfdWjG