首页 > 代码库 > 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)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。