這里的問題是將所有零放在陣列的末尾。
我已經撰寫了下面的代碼，但是在傳遞(arr, n)給pushzero()函式之后，當我嘗試列印陣列時，它什么也不做，并且呼叫函式n后的值變為零。pushzero()
#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;
}
uj5u.com熱心網友回復：
代碼具有未定義的行為，因為內部回圈pushzero迭代得太遠：
- 在 的外回圈的最后一次迭代中
pushzero，i具有值n - 1 - 內部回圈的最后一次迭代
j具有值i，因此n - 1， - 如果測驗
arr[j] == 0為真（由于陣列中有多個零，這將發生），swap將呼叫以交換 and 的值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 2 )復雜度。下面是一個更簡單的線性執行時間：
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 ]);
}
}
}
正如@PaulMcKenzie所建議的，您還可以使用更慣用的 C 解決方案：
#include <algorithm>
void pushzero(int arr[], int len) {
std::stable_partition(arr, arr len, [](int n) { return n != 0; });
}
uj5u.com熱心網友回復：
您可以通過使用 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
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/489012.html
上一篇：如何按ID對卡片物件進行排序