程序员经典面试题:数组旋转算法
发布时间:2020-12-16 07:46:13 所属栏目:百科 来源:网络整理
导读:今天PHP站长网 52php.cn把收集自互联网的代码分享给大家,仅供参考。 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如数组{3,4,5,1
以下代码由PHP站长网 52php.cn收集自互联网 现在PHP站长网小编把它分享给大家,仅供参考
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,5}的一个旋转,该数组的最小值为1。 (如果数组里有重复元素,怎么办?)
答 案: 2分查找的扩充,考虑 [from,to]这段区间,mid = (from + to) / 2,如果a[mid] < a[to] 则最小值在前半段里,如果a[mid] > a[to],这段区间发生了跳变,所以最小值在后半段区间里。相等时,当然我们可以比较a[mid]和a[from],但再相等就没办法了。偷懒的做法是直接从前后半 段分别找,然后返回最小的,因此最差时间复杂度是O(n)。当存在相等的数时,可能达到最差时间复杂度。 #include<iostream> using namespace std; int a[1000005]; int find(int *a,int from,int to) { if (from == to - 1) { return (a[from] < a[to])?a[from]:a[to]; } if (from == to) { return a[to]; } int mid = (from + to) >> 1,x; if (a[mid] < a[to]) { x = find(a,from,mid - 1); if (x > a[mid]) { x = a[mid]; } } else if (a[mid] > a[to]) { x = find(a,mid + 1,to); } else { int x1 = find(a,mid - 1); int x2 = find(a,to ); x = (x1 < x2)?x1:x2; if (x > a[mid]) { x = a[mid]; } } return x; } int main() { int i,n; while (scanf("%d",&n) != EOF) { for (i = 0; i < n; ++i) { scanf("%d",a + i); } printf("%dn",find(a,n -1)); } return 0; } 以上内容由PHP站长网【52php.cn】收集整理供大家参考研究 如果以上内容对您有帮助,欢迎收藏、点赞、推荐、分享。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |