leetcode之Find Minimum in Rotated Sorted Array 问题
问题描述:
Suppose an array sorted in ascending(升序) order is rotated at some pivot(枢轴; 中心点) unknown to you beforehand(提前,事先).
(i.e., 0 1 2 4 5 6 7
might become 4 5 6 7 0 1 2
).
Find the minimum element.
You may assume no duplicate exists in the array.
示例:其实上面已经给出了,不完全是升序的,有可能是旋转了一下的,在计算机组成原理中和"移位"的意思差不多吧。
题目来源:Find Minimum in Rotated Sorted Array (https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/#/description)
思路:其实这道题很容易就想到二分查找来查找指定数字,因为这个数组本身是有序的或者说是局部有序的,自然而然折半查找的效率高,快。熟悉二分查找的同学就可以跳过接下来的思路分析了,下面简单介绍一下二分查找是咋个查法。以这道题给的案例进行分析:
1)首先你得定义三个个指针,其中呢,需要一个首指针一个尾指针,在这我记作low和high,分别指向数组索引为0的位置,high自然而然就指向索引为n - 1(n代表的就是数组长度),另外需要一个指向数组中间元素的指针,记作mid,由定义就知道它应该是等于(low + high) / 2,但是一般不这么写,因为当数组长度比较大的时候,容易溢出。常见写法其实是这样的:mid = low + (high - low) / 2;
2)接下来就是比较数值大小了呗,在这比较nums[mid]和nums[high]的值大小,如果前者小于后者,说明后半部分是升序的喽,最小值能在后半部分呢?所以转向前半部分,变换一下指针,令high = mid ;相反就令low = mid + 1,一样的意思,在这就不重复赘述了;
3)最后low指针所指向的不就是最小的值嘛?那就返回它不就完了?
代码:
在这小小的卖个关子,题目给出的是没有重复的数字,要是有重复的数字咋办呢?会有哪里不一样的吗?题目详情可以参见:Find Minimum in Rotated Sorted Array,详细解答可以参考:Find
Minimum in Rotated Sorted Array解答