c++ - n 作为参数传递给函数后为 0，这里似乎有什么问题？

Question

这里的问题是将所有零放在数组的末尾。 我编写了下面的代码，但是将 (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是 true，因为数组中有多个零，所以会发生这种情况， 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; });
}