首页 > 代码库 > 1101. Quick Sort (25)

1101. Quick Sort (25)

quick sort的pivot一定会在排序后应该在的位置上,利用这点,如果pivot再正确位置上,还有pivot之前的数小于pivot(也暗示了pivot之后的数都大于他,因为pivot再对的位置上)。。。大神的思路果然很厉害。。。一开始写了半天还超时了。。。

#include<iostream>
#include<string>
#include<map>
#include<vector>
#include<algorithm>
#include<queue>
#include<set>
#include<stack>
using namespace std;


        

int main() {
    
    int num;
    cin >> num;
    vector<int> arr;
    vector<int> ori;
    for (int i = 0; i < num; i++) {
        int temp;
        cin >> temp;
        ori.push_back(temp);
        arr.push_back(temp);
    }

    sort(arr.begin(), arr.end());
    vector<int> ans;
    int c=0;
    int max = 0;
    for (int i = 0; i < num; i++) {
        if (ori[i] == arr[i] && ori[i]>max) {
            c++;
            ans.push_back(arr[i]);
        }

        if (ori[i] > max) {
            max = ori[i];
        }
    }

    cout << c << endl;

    for (int i = 0; i < ans.size(); i++) {
        if (i == 0) {
            cout << ans[i];
        }

        else
            cout <<   << ans[i];
    }
    

    system("pause");
    
}

 

1101. Quick Sort (25)