首页 > 代码库 > [算法]找出数组当中的中枢元素
[算法]找出数组当中的中枢元素
给定一个整型数组，找出pivot，使得对于任意i < pivot,a[i] <=a[pivot],对于i > pivot，a[i]>=a[pivot]，只能用一个额外的数组，和少量空间。
思路
1、使用一个数组t记录，t[i]记录的是a[0]~a[i]的最大值
int *t = new int[n];for(int i = 0, max = ~0; i < n; ++i){ if(a[i] > max){ max = a[i]; } t[i] = max;}
2、从a的尾部首部遍历，使用min记录a[i]~a[n-1]的最小值，倘若min >= t[i]，表示i 即为中枢元素的索引
int pivot =-1;for(int i = n-1, min = 0x7fffffff; i >= 0; --i){ if(a[i] < min){ min = a[i]; } if(min >= t[i]){ pivot = i; break; }}delete[] t;
本文基于知识共享署名-非商业性使用 3.0 许可协议进行许可。欢迎转载、演绎，但是必须保留本文的署名林羽飞扬,若需咨询，请给我发信
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。