有做外贸的平台网站吗,网站首页做跳转,中小企业网站制作哪家好,wordpress中调用分类目录文章列表描述 著名的快速排序算法里有一个经典的划分过程#xff1a;我们通常采用某种方法取一个元素作为主元#xff0c;通过交换#xff0c;把比主元小的元素放到它的左边#xff0c;比主元大的元素放到它的右边。 给定划分后的 N 个互不相同的正整数的排列#xff0c;请问有多少…描述 著名的快速排序算法里有一个经典的划分过程我们通常采用某种方法取一个元素作为主元通过交换把比主元小的元素放到它的左边比主元大的元素放到它的右边。 给定划分后的 N 个互不相同的正整数的排列请问有多少个元素可能是划分前选取的主元 例如给定 N 5 , 排列是1、3、2、4、5。则 1.1 的左边没有元素右边的元素都比它大所以它可能是主元 2.尽管 3 的左边元素都比它小但其右边的 2 比它小所以它不能是主元 3.尽管 2 的右边元素都比它大但其左边的 3 比它大所以它不能是主元 4.类似原因4 和 5 都可能是主元。 因此有 3 个元素可能是主元。 输入 输入在第 1 行中给出一个正整数 N≤10^5 第 2 行是空格分隔的 N 个不同的正整数每个数不超过 10^9。 输出 在第 1 行中输出有可能是主元的元素个数在第 2 行中按递增顺序输出这些元素其间以 1 个空格分隔行首尾不得有多余空格。 样例输入
5 1 3 2 4 5
样例输出
3 1 4 5
code1wrong 我一开始的代码是判断nums[i]左边是否存在大于nums[i]的数字有就break 右边同理nums[i]右边是否存在小于nums[i]的数字有就break但这样就会超时因为N≤10^5 else if(!pd_left(nums,i)!pd_right(nums,i)) result.push_back(nums[i]);这句代码复度为On*n #includeiostream
#includevector
#includealgorithm
using namespace std;
bool pd_right(vectorintnums,const int j){int min_numnums[j];bool flag1false;for(int ij1;inums.size();i){min_nummin(min_num,nums[i]);if(min_numnums[j]){flag1true;break;} }return flag1;
}
bool pd_left(vectorintnums,const int j){bool flag2false;int max_numnums[j];for(int ij-1;i0;i--){max_nummax(max_num,nums[i]);if(max_numnums[j]){flag2true;break;}}return flag2;
}
int main()
{int n;while(cinn){//vectorint nums(n);vectorint nums;for(int i0;in;i){int num;cinnum;nums.push_back(num);}vectorintresult;for(int i0;inums.size();i){if(i0(!pd_right(nums,i))) result.push_back(nums[i]);else if(!pd_left(nums,i)!pd_right(nums,i)) result.push_back(nums[i]);else if(inums.size()-1(!pd_left(nums,i))) result.push_back(nums[i]);//O(n*n)}sort(result.begin(),result.end()); coutresult.size()endl;if(result.size()0){for(int i0;iresult.size()-1;i) coutresult[i] ;coutresult[result.size()-1];}coutendl;}return 0;
}
code2AC版 用到动态规划使复杂度变为O(n使用两个数组maxLeft和minRight来保存每个元素的左边的最大值和右边的最小值。通过一次遍历分别计算出每个元素的左边的最大值和右边的最小值然后再进行一次遍历判断每个元素是否是主元 #includeiostream
#includevector
#includealgorithm
using namespace std;
int main()
{int n;while(cinn){vectorintmaxleft(n);vectorintminright(n);vectorintnums(n);for(int i0;in;i){//int num;cinnums[i];//nums.push_back(num);}maxleft[0]nums[0];for(int i1;in;i){maxleft[i]max(maxleft[i-1],nums[i]);}minright[n-1]nums[n-1];for(int in-2;i0;i--){minright[i]min(minright[i1],nums[i]);}vectorintresult;for(int i0;in;i){if(nums[i]maxleft[i]nums[i]minright[i]){result.push_back(nums[i]);}}sort(result.begin(),result.end());coutresult.size()endl;if(result.size()0){for(int i0;iresult.size()-1;i) coutresult[i] ;if(result.size()0) coutresult[result.size()-1];}coutendl;return 0;}
}
