Find Minimum in Rotated Sorted Array-K6K4.com

原题： https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/description/

题意： 假设一个排好序的数组在某处执行了一次“旋转”(例如0 1 2 4 5 6 7旋转成4 5 6 7 0 1 2)，找出最小的元素。

约定：（1）数组中元素没有重复。

标签： rotated、minimum、sorted、旋转、某处、面试

猜你感兴趣的圈子：

LeetCode交流圈

Bingo

2017-08-14 18:28:25 1楼#1层

Python解法一：二分法

class Solution(object):
    def findMin(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        low, high = 0, len(nums) - 1
        while low < high:
            mid = (low + high) / 2
            if nums[mid] <= nums[high]: #min位于左侧上升沿
                high = mid
            else: #min位于左侧上升沿与右侧上升沿之间
                low = mid + 1
        return nums[low]

Bingo

2017-08-14 18:29:03 2楼#1层

Python解法二：线性枚举法

class Solution:
    # @param num, a list of integer
    # @return an integer
    def findMin(self, num):
        return min(num)

Bingo

2017-08-14 18:29:31 3楼#1层

C++：

class Solution {
public:
    int findMin(vector<int> &num) {
        int left = 0, right = num.size() - 1;
        if (num[left] > num[right]) {
            while (left != (right - 1)) {
                int mid = (left + right) / 2;
                if (num[left] < num[mid]) left = mid;
                else right = mid;
            }
            return min(num[left], num[right]);
        }
        return num[0];
    }
};

取消

回复

推荐圈子

LeetCode交流圈