【算法入门02】旋转数组的最小数字

【算法入门02】旋转数组的最小数字

核心考点：数组理解，二分查找，临界条件

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}是数组{1, 2, 3, 4, 5}的一个旋转，该数组的最小值为1。NOTE：给出的所以元素都大于0，若数组大小为0，请返回0。

解析一：（不提倡） 寻找数组当中的最小值，不管怎么说，遍历一遍数组当中元素是肯定能找到的。

class Solution {public: int minNumberInRotateArray(vector rotateArray) { if (rotateArray.size() == 0) //数组大小为0，返回0 return 0; int min = rotateArray[0]; //遍历数组寻找最小值 for (size_t i = 1; i < rotateArray.size(); i++) { if (rotateArray[i] < min) min = rotateArray[i]; } return min; //返回最小值 }};

解析二：（较提倡）

因为原数组是一个非递减的数组，所以原数组当中的每一个元素都大于或等于其前面的一个元素，而原数组经过旋转后被分为两部分（一部分是被旋转到后面的，另一部分是未被旋转的），这两部分也分别满足该规律（每一个元素都大于或等于其前面一个元素）。

所以我们可以挨个比较数组当中相邻的两个元素，若前一个元素小于或等于后一个元素，则继续比较；若前一个元素大于后一个元素，则说明这两个元素之间就是分界处，此时返回后一个元素即可。

若是遍历完数组都没有找到前一个元素大于后一个元素的情况，则说明旋转数组是由原数组的全部元素旋转后得到的（旋转后的数组与原数组相同），此时返回数组的第一个元素即为最小值。

该解法找到特定情况后便可以直接返回数组当中的最小值，相对于第一种解法来说效率会高一点，但其查找效率的快慢却决于数组的旋转深度。

class Solution {public: int minNumberInRotateArray(vector rotateArray) { if (rotateArray.size() == 0) //数组大小为0，返回0 return 0; for (size_t i = 1; i < rotateArray.size(); i++) { if (rotateArray[i - 1] > rotateArray[i]) //找到前一个元素小于后一个元素的情况 return rotateArray[i]; //返回后者即为最小值 } return rotateArray[0]; //数组遍历结束，返回数组的第一个元素即为最小值 }};

解析三：（正解） 对于该题目，我们还可以使用二分查找的方式：找到数组的中间元素mid，将mid与某一元素进行比较，确定最小值位于mid的哪一侧，从而达到查找一次后待查找元素减半的效果。

这里我们选择将中间元素mid与数组的最后一个元素进行比较（也可以选择将其与第一个元素进行比较），那么会出现以下四种情况：

情况一： left索引的元素小于right索引的元素。

此时说明[left, right]区间内的元素已经是非递减序列了，left索引的元素便是数组当中的最小值。情况二： mid索引的元素小于right索引的元素。

此时说明[mid+1, right]区间内的元素都大于等于mid索引的元素，而mid左侧还有可能有比mid索引的元素更小的元素，所以将待查找区间缩小为[left, mid]。情况三： mid索引的元素大于right索引的元素。

此时说明[left, mid]区间内的元素都大于等于right索引的元素，而在mid和right之间可能有比right索引的元素更小的元素，所以将待查找区间缩小为[mid+1, right]。情况四： mid索引的元素等于right索引的元素。

此时无法判断数组最小值位于mid的哪一侧，我们可以选择将right左移一个位置，然后重新进行判断。

通过这种方法一直判断下去，直到出现第一种情况得到最小值，或是直到left和right所确定的区间当中只有一个元素时，这一个元素便是数组当中的最小值。

class Solution {public: int minNumberInRotateArray(vector rotateArray) { if (rotateArray.size() == 0) //数组大小为0，返回0 return 0; int left = 0, right = rotateArray.size() - 1; while (left < right) { if (rotateArray[left] < rotateArray[right]) //[left,right]区间已经是非递减序列，返回区间内第一个元素即可 return rotateArray[left]; int mid = left + (right - left) / 2; if (rotateArray[mid] < rotateArray[right]) //待查找区间缩小为[left, mid] { right = mid; } else if (rotateArray[mid] > rotateArray[right]) //待查找区间缩小为[mid+1, right] { left = mid + 1; } else //mid和right索引的元素值相同，将right往左移 { right--; } } return rotateArray[left]; //left和right所确定的区间当中只有一个元素，返回这个元素即可 }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。