首页 > 编程语言 > 详细

面试题11. 旋转数组的最小数字

时间:2020-05-09 15:12:32      阅读:35      评论:0      收藏:0      [点我收藏+]

题目:

 

解答:

(1)如下图所示,寻找旋转数组的最小元素即为寻找 右排序数组 的首个元素 numbers[x] ,称 x 为 旋转点 。

(2)排序数组的查找问题首先考虑使用 二分法 解决,其可将遍历法的 线性级别 时间复杂度降低至 对数级别 。

技术分享图片

 

 

算法流程:

(1)循环二分:设置 i, j 指针分别指向 numbers 数组左右两端,m = (i + j) // 2为每次二分的中点( "//" 代表向下取整除法,因此恒有i≤m<j ),可分为以下三种情况:

  A.  当 numbers[m] > numbers[j]时: m 一定在 左排序数组 中,即旋转点 x 一定在 [m + 1, j]闭区间内,因此执行 i = m + 1;

  B.  当 numbers[m] < numbers[j] 时: m 一定在 右排序数组 中,即旋转点 xx 一定在[i, m]闭区间内,因此执行 j = m;

  C.  当 numbers[m] == numbers[j] 时: 无法判断 m 在哪个排序数组中,即无法判断旋转点 x 在 [i, m]还是 [m + 1, j]区间中。解决方案: 执行 j = j - 1缩小判断范围 (分析见以下内容) 。

(2)返回值:当i == j时跳出二分循环,并返回numbers[i]即可。

 1 class Solution {
 2 public:
 3     int minArray(vector<int>& numbers) 
 4     {
 5         int left = 0;
 6         int right = numbers.size() - 1;
 7         while (left < right)
 8         {
 9             int mid = left + (right - left) / 2;
10             if (numbers[mid] > numbers[right])
11             {
12                 left = mid + 1;
13             }
14             else if (numbers[mid] < numbers[right])
15             {
16                 right = mid;
17             }
18             else
19             {
20                 right--;
21             }
22         }
23 
24         return numbers[left];
25     }
26 };

 

面试题11. 旋转数组的最小数字

原文:https://www.cnblogs.com/ocpc/p/12856941.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!