153. Find Minimum in Rotated Sorted Array

太过爱你忘了你带给我的痛 2022-03-07 05:04 182阅读 0赞

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.

Example 1:

Input: [3,4,5,1,2] 
    Output: 1

Example 2:

Input: [4,5,6,7,0,1,2]
    Output: 0

难度：medium

题目：假设一个按升序排序的数组在某个未知的轴上旋转。假定数组中没有重复元素。

思路：分情况二叉搜索

![clipboard.png][]

Runtime: 0 ms, faster than 100.00% of Java online submissions for Find Minimum in Rotated Sorted Array.  
Memory Usage: 37.6 MB, less than 100.00% of Java online submissions for Find Minimum in Rotated Sorted Array.

class Solution {
        public int findMin(int[] nums) {
            return findMin(nums, 0, nums.length - 1);
        }
        
        public int findMin(int[] nums, int left, int right) {
            int mid = left + (right - left) / 2;
            // 升序
            if (nums[left] <= nums[mid] && nums[mid] <= nums[right]) {
                return nums[left];
            }
            // 降序
            if (nums[left] >= nums[mid] && nums[mid] >= nums[right]) {
                return nums[right];
            }
            // 升序占大降序占小
            if (nums[left] >= nums[mid]) {
                return findMin(nums, left, mid);
            } 
            // 升序占小降序占大
            return findMin(nums, mid, right);
        }
    }

[clipboard.png]: /images/20220307/4069e718bd124c95953121a1da69fd56.png

发表评论取消回复

表情：

评论列表（有 0 条评论，182人围观）

还没有评论，来说两句吧...

相关阅读

相关 Find Minimum in Rotated Sorted Array II--LeetCode

> Follow up for "Find Minimum in Rotated Sorted Array": > What if duplicates are allow

￡神魔★判官ぃ/ 2022年08月07日 12:58/ 0 赞/ 154 阅读

相关 Leetcode: Find Minimum in Rotated Sorted Array

题目： Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e.,

谁践踏了优雅/ 2022年08月07日 09:47/ 0 赞/ 4 阅读

相关 LeetCode154—Find Minimum in Rotated Sorted Array II

原题 [原题链接][Link 1] > Follow up for “Find Minimum in Rotated Sorted Array”: > What i

逃离我推掉我的手/ 2022年07月15日 12:26/ 0 赞/ 101 阅读

相关 LeetCode154—Find Minimum in Rotated Sorted Array II

原题 [原题链接][Link 1] > Follow up for “Find Minimum in Rotated Sorted Array”: > What i

心已赠人/ 2022年07月15日 12:26/ 0 赞/ 112 阅读

相关 LeetCode153—Find Minimum in Rotated Sorted Array

原题 [原题链接][Link 1] > Suppose a sorted array is rotated at some pivot unknown to you b

不念不忘少年蓝@/ 2022年07月15日 10:12/ 0 赞/ 111 阅读

相关 [Leetcode]153. Find Minimum in Rotated Sorted Array

Obviously this question can be solved within `O(n)` time by traversing the whole array a

怼烎@/ 2022年07月12日 09:22/ 0 赞/ 155 阅读

相关 153. Find Minimum in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you befor

太过爱你忘了你带给我的痛/ 2022年03月07日 05:04/ 0 赞/ 182 阅读

相关 [LeetCode] Find Minimum in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., `0 1

朴灿烈づ我的快乐病毒、/ 2021年12月03日 07:29/ 0 赞/ 144 阅读

相关 LeetCode-153 Find Minimum in Rotated Sorted Array

题目描述 Suppose an array sorted in ascending order is rotated at some pivot unknown to you

爱被打了一巴掌/ 2021年11月16日 23:48/ 0 赞/ 205 阅读

相关 153. Find Minimum in Rotated Sorted Array(leetcode, binary search)

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/description/ leetcod

╰+哭是因爲堅強的太久メ/ 2021年09月30日 14:38/ 0 赞/ 214 阅读