P1923：深入解析与优化策略

一、手写快排最后两个测试数据超时了&＃xff0c;预料之中的事情&＃xff0c;因为这个题目考的应该就是O(n)的算法

二、看题解有人用STL的nth_element过掉本题&＃xff0c;我直接略过这种解法

三、快读&＃43;快速排序(手写)&＃43;-O2优化 &＃xff08;三者缺一不可&＃xff09;可以过掉此题&＃xff0c;但O(nlogn)的算法不是预期的解法

代码如下&＃xff1a;

#include
#include
#include
using namespace std;int nums[5000005];void qsort(int left, int right){int x &＃61; left, y &＃61; right, mid &＃61; nums[(left&＃43;right)>>1];while(x<&＃61;y){while(nums[x]<mid)x&＃43;&＃43;;while(mid<nums[y])y--;if(x<&＃61;y){int tmp &＃61; nums[x];nums[x] &＃61; nums[y];nums[y] &＃61; tmp;x&＃43;&＃43;;y--;}}//left, y, x, rightif(left<y)qsort(left, y);if(x<right)qsort(x, right);
}inline int read(){//快速读入 int x&＃61;0,f&＃61;1;char c&＃61;getchar();while(c<&＃39;0&＃39;||c>&＃39;9&＃39;){if(c&＃61;&＃61;&＃39;-&＃39;)f&＃61;-1;c&＃61;getchar();}while(c>&＃61;&＃39;0&＃39;&&c<&＃61;&＃39;9&＃39;){x&＃61;(x<<1)&＃43;(x<<3)&＃43;(c^48);c&＃61;getchar();} return x*f;
}int main(){int cnt, k;//scanf("%d %d", &cnt, &k);cnt &＃61; read();k &＃61; read();if(k>cnt-1)return -1;for(int i&＃61;0;i<cnt;i&＃43;&＃43;){nums[i] &＃61; read();}qsort(0, cnt-1);cout<<nums[k]<<endl;return 0;
}


四、vector &＃43; O(n)的算法有些时候会超时

说有些时候&＃xff0c;是因为&＃xff0c;运气好的时候&＃xff0c;第五组测试数据就900多ms&＃xff0c;刚刚好不会超时&＃xff0c;但是有时候运气差&＃xff08;我第二次提交这个代码就遇到了&＃xff0c;由此看概率不低&＃xff09;&＃xff0c;就会超过1s&＃xff0c;然后TLE

代码如下&＃xff1a;

#include
#include
#include
using namespace std;void kthsmall(vector<int>& nums, int left, int right, int k, int* res){int x &＃61; left, y &＃61; right, mid &＃61; nums[(x&＃43;y)>>1];while(x<&＃61;y){while(nums[x]<mid)x&＃43;&＃43;;while(mid<nums[y])y--;if(x<&＃61;y){int tmp &＃61; nums[x]; nums[x] &＃61; nums[y]; nums[y] &＃61; tmp;x&＃43;&＃43;;y--;}}//left<&＃61;y<&＃61;x<&＃61;rightif(k<&＃61;y)kthsmall(nums, left, y, k, res);else if(x<&＃61;k)kthsmall(nums, x, right, k, res);else{*res &＃61; y&＃43;1;return;}
}int main(){int cnt, k;cin>>cnt>>k;vector<int> nums;for(int i&＃61;0;i<cnt;i&＃43;&＃43;){int tmp;//cin>>tmp;scanf("%d", &tmp);nums.push_back(tmp);}int res &＃61; 0;kthsmall(nums, 0, nums.size()-1, k, &res);cout<<nums[res]<<endl;return 0;
}


超时详情

五、换成数组 &＃43; O(n)的算法&＃xff0c;通过了&＃xff0c;而且时间很好看

代码如下&＃xff1a;

#include
#include
#include
using namespace std;int nums[5000005];void kthsmall(int left, int right, int k, int* res){int x &＃61; left, y &＃61; right, mid &＃61; nums[(x&＃43;y)>>1];while(x<&＃61;y){while(nums[x]<mid)x&＃43;&＃43;;while(mid<nums[y])y--;if(x<&＃61;y){int tmp &＃61; nums[x]; nums[x] &＃61; nums[y]; nums[y] &＃61; tmp;x&＃43;&＃43;;y--;}}//left<&＃61;y<&＃61;x<&＃61;rightif(k<&＃61;y)kthsmall(left, y, k, res);else if(x<&＃61;k)kthsmall(x, right, k, res);else{*res &＃61; y&＃43;1;return;}
}int main(){int cnt, k;cin>>cnt>>k;for(int i&＃61;0;i<cnt;i&＃43;&＃43;){scanf("%d", &(nums[i]));}int res &＃61; 0;kthsmall(0, cnt-1, k, &res);cout<<nums[res]<<endl;return 0;
}


好看的时间&＃xff08;最多600多ms&＃xff0c;十分nice&＃xff09;

六、后记&＃xff0c;O(n)的算法还需要好好研究&＃xff0c;我自己没有看懂&＃xff0c;自己其实一开始尝试写O(n)的算法了&＃xff0c;但是总是出错&＃xff0c;我也不知道为什么。而且对于函数中的while循环和递归函数&＃xff0c;我都理不清楚出口的样子。先背过吧。 已经弄明白了&＃xff0c;讲解如下&＃xff1a;

2020年08月21日&＃xff0c;通过循环不变量&＃xff08;loop invariant&＃xff09;想明白这个过程了。

while(x<&＃61;y){while(nums[x]<mid)x&＃43;&＃43;;while(mid<nums[y])y--;if(x<&＃61;y){int tmp &＃61; nums[x]; nums[x] &＃61; nums[y]; nums[y] &＃61; tmp;x&＃43;&＃43;;y--;}}


这个while循环&＃xff0c;最终的跳出循环时的条件是(y&＃xff0c;并且保证了nums[left]<&＃61;nums[y]<&＃61;nums[x]<&＃61;nums[right]&＃xff0c;若y和x之间有空隙&＃xff0c;则空隙中的值作为nums数组索引下标所对应的所有nums中的值都是相等的&＃xff0c;这是while循环能够保证的。