不改变正负数相对顺序重新排列数组

题目

• 不改变正负数相对顺序重新排列数组

思路

• 块翻转，如果出现第奇数次”+..+-…-“这种块，则反转变成”-…-+…+”，因为每次扫描只是翻转不相邻的(正正…正负…负负)串，因此所有被翻转的串，从正负数分界处被分为两部分，分别归入前后两个相邻的(正正…正负…负负)串。因此，每趟扫描能消灭一半的(正正…正负…负负)串。最终，总共需要扫描的次数最多为logN。
• 参考:Link

代码

#include<iostream>
#include<vector>
using namespace std;

void reverse(vector<int>& nums, int start, int end)
{
    int i=start, j=end;
    while(i<j)
    {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
        i++;
        j--;
    }
}

void reverse_block(vector<int>& nums, int start, int mid, int end)
{
    reverse(nums, start, mid);
    reverse(nums, mid+1, end);
    reverse(nums, start, end);
}

int main()
{
    int n;
    cin>>n;
    vector<int> nums(n, 0);
    for(int i=0;i<n;i++)
        cin>>nums[i];

    while(1)
    {
        int p_and_n = 0; //表示“正...正负...负”这种格式的串的个数
        int index = 0;//索引
        int p_start = 0;//正数的开始位置
        int p_end = 0;//正数的结束位置
        int n_end = 0;//负数的结束位置
        bool pre_p = false; //表示之前是正
        bool r = true; //是否需要反转，第奇数个正负需要翻转
        while(index<nums.size())
        {
            if(nums[index]>0)
            {
                p_start = index;
                while(index+1<nums.size() && nums[index+1]>0)
                    index++;
                p_end = index;
                pre_p = true;
            }
            else if(nums[index]<0)
            {
                while(index+1<nums.size() && nums[index+1]<0)
                    index++;
                n_end = index;
                if(pre_p)
                    p_and_n++;
                if(pre_p && r)//如果前面的为正数，且当前可反转
                {
                    reverse_block(nums, p_start, p_end, n_end);
                    r = !r;
                    pre_p = !pre_p;
                }
            }
            index++;
        }
        if(p_and_n==0)
            break;
    }

    //输出
    for(int i=0;i<nums.size();i++)
        cout<<nums[i]<<endl;
    system("pause");
    return 0;
}