当前位置:
ag凯发k8国际 >
前端技术
> javascript
>内容正文
javascript
《剑指offer》— javascript(6)旋转数组的最小数字 -ag凯发k8国际
ag凯发k8国际
收集整理的这篇文章主要介绍了
《剑指offer》— javascript(6)旋转数组的最小数字
小编觉得挺不错的,现在分享给大家,帮大家做个参考.
旋转数组的最小数字
题目描述
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。
note:给出的所有元素都大于0,若数组大小为0,请返回0。
实现代码
function minnumberinrotatearray(rotatearray) {var len = rotatearray.lengthif (len == 0){return 0}else{ var low = 0;var high = len-1;while(low思路
旋转之后的数组实际上可以划分成两个有序的子数组:前面子数组的大小都大于后面子数组中的元素,实际上最小的元素就是两个子数组的分界线。
我们用两个指针low和high分别指向数组的第一个元素和最后一个元素。按照题目的旋转的规则,第一个元素应该是大于等于最后一个元素的;但是如果不是旋转,第一个元素肯定小于或等于最后一个元素。
找到数组的中间元素。中间元素大于最后一个元素,则中间元素位于前面的递增子数组,此时最小元素位于中间元素的后面。我们可以让第一个指针low指向中间元素。
中间元素小于最后一个元素,则中间元素位于后面的递增子数组,此时最小元素位于中间元素的前面。我们可以让第二个指针high指向中间元素。
中间元素等于最后一个元素,则将第二个指针向前移,然后继续比较。
转载于:https://www.cnblogs.com/echovic/p/6430643.html
总结
以上是ag凯发k8国际为你收集整理的《剑指offer》— javascript(6)旋转数组的最小数字的全部内容,希望文章能够帮你解决所遇到的问题。
- 上一篇:
- 下一篇: