c++ 反转数组而不改变零位

bvhaajcl  于 2022-12-24  发布在  其他
关注(0)|答案(6)|浏览(170)

我刚刚和朋友们沿着尝试了一些数据结构的问题,我从一个朋友那里遇到了这个问题,他也不能解决这个问题。
问题:反转数组而不改变零的位置。例如:如果数组具有057809,则结果应为098705。
我试过了,但它并不能在所有情况下都正确地做,我很抱歉,如果代码看起来很丑,我现在是一个新手。

#include<iostream>
using namespace std;
int main()
{
    int arr[100], tot, i, j, temp;
    cout<<"Enter the Size for Array: ";
    cin>>tot;
    cout<<"Enter "<<tot<<" Array Elements: ";
    for(i=0; i<tot; i++)
        cin>>arr[i];
    cout<<"\nThe Original Array is:\n";
    for(i=0; i<tot; i++)
        cout<<arr[i]<<" ";
    j = tot-1;
    for(i=0; i<j; i++, j--)
    {
        if(arr[i] == 0) {
            i++;
            continue;
        }else if(arr[j] == 0) {
           j--;
           continue;
        }
        else {
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    cout<<"\n\nThe Reverse of Given Array is:\n";
    for(i=0; i<tot; i++)
        cout<<arr[i]<<" ";
    cout<<endl;
    return 0;
}

我已经尝试了上面的代码,但它没有给予出正确的结果。

lqfhib0f

lqfhib0f1#

这里的问题是,在循环的每次迭代中都要修改循环变量ij;只有在元素被交换的情况下才需要更新它:

for(i=0; i<j;)
{
    if(arr[i] == 0) {
        i++;
    }else if(arr[j] == 0) {
       j--;
    }
    else {
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        ++i;
        --j;
    }
}

www.example.com上的演示godbolt.org

mqkwyuun

mqkwyuun2#

看来你需要下一个循环逻辑:

i = 0;
j = tot-1;
while(i<j)   {
        while (arr[i]==0 && i<j)
            i++;
        while (arr[j]==0 && j>i) 
           j--;
        if (i < j) {
          temp = arr[i];
          arr[i] = arr[j];
          arr[j] = temp;
        }
       i++;
       j--; 
    }
imzjd6km

imzjd6km3#

您可以使用两个指针进行切换,只需跳过任何0。

#include<iostream>
using namespace std;
int main()
{
    int arr[100], tot, i, j, temp;
    cout<<"Enter the Size for Array: ";
    cin>>tot;
    cout<<"Enter "<<tot<<" Array Elements: ";
    for(i=0; i<tot; i++)
        cin>>arr[i];
    cout<<"\nThe Original Array is:\n";
    for(i=0; i<tot; i++)
        cout<<arr[i]<<" ";
    i = 0, j = tot-1;
    while (i < j) {
        if (arr[i]!=0 && arr[j]!=0) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        } else if (arr[i] == 0) {
            i++;
        } else {
            j--;
        }
    }
   
    cout << "\n Reverse all elements of the array: " << endl;  
    // use for loop to print the reverse array  
    for ( i = 0; i < tot; i++)  
    {  
        cout << arr[i] << " ";  
    }  
    cout<<endl;
    return 0;
}

您可以在这里看到这一点:https://godbolt.org/z/84q3McccW

ryoqjall

ryoqjall4#

在循环中的代码中:

if(arr[i] == 0) {
        i++;
        continue;
    }else if(arr[j] == 0) {
       j--;
       continue;

arr[i]是一个0时,你递增i,但是当你continue时,在下一次迭代中,i作为i++, j--的一部分再次递增,这会使你的代码跳过元素,我建议使用std::vector和迭代器:

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> x{1,2,0,3,4,0,0,0};
    auto begin = x.begin();
    auto end = std::prev(x.end());

    while (begin != end) {
        while(begin != end && *begin == 0) ++begin;
        while(begin != end && *end == 0) --end;    
        if (begin != end) {
            std::swap(*begin,*end);
            ++begin;
            if (begin != end) --end;
        }
    }
    for (const auto& e : x) std::cout << e << " ";
}

output

4 3 0 2 1 0 0 0

代码从第一个元素和最后一个元素的迭代器开始,在循环中,当它们引用0并且两个元素还没有交叉时,它们会前进,然后交换元素。
如果额外的内存是可以接受的,一个更简单的解决方案是将所有非零元素复制到第二个std::vectorstd::reverse向量,然后再复制回来。

sr4lhrrt

sr4lhrrt5#

如果没有要跳过的零,则代码可以是

for (i= 0, j= n-1; i < j; i++, j--)
{
  Swap(a[i], a[j]);
}

现在,跳过零就足够了,这就给出了修改后的代码

for (i= 0, j= n-1; i < j; i++, j--)
{
  while (i < j && a[i] == 0) i++;
  while (i < j && a[j] == 0) j--;
  Swap(a[i], a[j]);
}

注意,交换可以用i==j来执行,这是无用的,但无害的,因为0 ≤ i ≤ j〈n。
更新:正如@fabian所做的那样,您可以将三个循环压缩为一个循环。

for (i= 0, j= n-1; i < j; )
{
  if (a[i] == 0) 
    i++;
  else if (a[j] == 0) 
    j--;
  else
  { 
    Swap(a[i], a[j]);
    i++; j--;
  }
}
ttp71kqs

ttp71kqs6#

你需要改变反转的逻辑。

#include<iostream>
using namespace std;
int main()
{
    int arr[100], tot, i, j, temp;
    cout<<"Enter the Size for Array: ";
    cin>>tot;
    cout<<"Enter "<<tot<<" Array Elements: ";
    for(i=0; i<tot; i++)
        cin>>arr[i];
    cout<<"\nThe Original Array is:\n";
    for(i=0; i<tot; i++)
        cout<<arr[i]<<" ";
    j = tot-1;
   for ( i = 0, j = tot - 1; i < tot/2; i++, j--)  
    {     
        temp = arr[i];  
        arr[i] = arr[j];  
        arr[j] = temp;  
    }  
    cout << "\n Reverse all elements of the array: " << endl;  
    // use for loop to print the reverse array  
    for ( i = 0; i < tot; i++)  
    {  
        cout << arr[i] << " ";  
    }  
    cout<<endl;
    return 0;
}

我希望这能帮上忙

相关问题