findingsea's Studio.

Find Minimum in Rotated Sorted Array I II@LeetCode

LeetCode
Word count: 324 / Reading time: 1 min
2015/05/05 Share

Find Minimum in Rotated Sorted Array

其实直接遍历也是可以也可以AC，但是更加优化的解法应该是采用二分查找的思想。如果中间值比起点大就收缩起点，如果中间值比终点大就收缩终点，直到收缩到起点和终点相邻，也就是找到了翻转的部分。这里需要注意的是，数组可能是没有翻转过的，所以mid的初值赋0。

实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public int findMin(int[] num) {
        int begin = 0, end = num.length - 1, mid = 0;
        while (num[begin] > num[end]) {
            if (end - begin == 1) {
                mid = end;
                break;
            }
            mid = (begin + end) / 2;
            if (num[begin] < num[mid])
                begin = mid;
            else 
                end = mid;
        }
        return num[mid];
    }
}

Find Minimum in Rotated Sorted Array II

理论上这题应该也用二分法，碰到起点终点相同的情况就只能进行遍历，但是那样代码会更复杂并且效率上并不见得提高多少，所以这里我直接采用遍历的方法。

实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    public int findMin(int[] num) {
        int min = num[0], length = num.length;
        if (num[0] >= num[length - 1]) {
            int index = 1;
            while (index < length) {
                if (num[index - 1] > num[index]) {
                    break;
                }
                index++;
            }
            min = index == length ? num[index - 1] : num[index];
        }
        return min;
    }
}

原文作者: findingsea

原文链接: http://findingsea.github.io/2015/05/05/find-minimum-in-rotated-sorted-array-i-ii-at-leetcode/

发表日期: May 5th 2015, 9:40:00 am

版权声明: 本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. Find Minimum in Rotated Sorted Array
  2. 2. Find Minimum in Rotated Sorted Array II
Total : 100
2020
2019
2018
2017
2015
2014
2013
Octopress GitHub Python Django 吐槽 Reading ACM 项目总结 JavaScript 日志 Java LeetCode Interview Algorithm Life Windows ffmpeg life Go c++ essay review