美文网首页
1101.Quick Sort

1101.Quick Sort

作者: 81f83b4769e0 | 来源:发表于2016-05-22 15:43 被阅读0次

    1101.Quick Sort

    题目分析

    Input:
    第一行:一个正整数N(N<=100000)
    第二行:N个互不相同的正整数,用空格分隔
    Output:
    第一行:符合条件的数的个数
    第二行:按照升序输出

    求解思路

    • int类型的数组arr[N]:存放了原始数据
    • maxBefore:当前左侧最大值(初始化为-1)
    • minBehind:当前右侧最小值(初始化为1000000005)
    • int类型的数组res[N]:存放结果
    • bool类型的数组flag[N]:flag[i]指示arr[i]是否为我们要找的元素,若是,flag[i]=true;否则flag[i]=false。
    1. 在输入的时候,假设当前输入为arr[i],判断arr[i]是否大于maxBefore,同时更新maxBefore和flag[i]的值。
    2. 逆序遍历数组,判断arr[i]是否小于minBehind,若不是,将flag[i]的值更新为false。若此时flag[i]为true,则arr[i]为我们要找的元素,存入res数组中。
    3. 输出时,若sum为0,则输出空的一行(必须输出空的一行,否则有的样例不能通过);若sum不为0,调用sort()函数,将res数组升序排列后输出。

    C++源码

    #include<iostream>
    #include<algorithm>
    using namespace std;
    
    int main()
    {
        int N;
        int sum = 0;
        cin>>N;
        bool *flag = new bool[N];
        int *arr = new int[N];
        int *res = new int[N];
        int maxBefore = -1;
        int minBehind = 1000000005;
    
        for(int i = 0; i < N; i++)
        {
            flag[i] = true;
        }
    
        for(int i = 0; i < N; i++)
        {
            cin>>arr[i];
            if(arr[i] > maxBefore)
            {
                maxBefore = arr[i];
            }
            else
            {
                flag[i] = false;
            }
        }
        for(int i = N - 1; i >= 0; i--)
        {
            if(arr[i] < minBehind)
            {
                minBehind = arr[i];
            }
            else
            {
                flag[i] = false;
            }
            if(flag[i])
            {
                sum = sum + 1;
                res[sum - 1] = arr[i];
            }
        }
        cout<<sum<<endl;
        if(sum == 0)
        {
            cout<<endl;
        }
        else
        {
            //res[0..sum-1]
            sort(res, res + sum);
            for(int i = 0; i < sum; i++)
            {
                cout<<res[i];
                if(i != sum - 1)
                {
                    cout<<" ";
                }
            }
        }
        return 0;
    }
    

    相关文章

      网友评论

          本文标题:1101.Quick Sort

          本文链接:https://www.haomeiwen.com/subject/sdworttx.html