问题描述:
Suppose a sorted array 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.
原问题链接:https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/
问题分析
在之前的文章里已经有过对于循环移动的排序数组进行元素查找的讨论。那时候是查找某个指定的元素,而这里只是查找数组里最小的元素。稍微有点差别。不过我们也可以借鉴这个思路。
对于一个移位数组来说,它本身就不再是一个单纯的从小到大的序列,它是由两个从小到大的序列组成。这样的话,这个最小的元素可能在数组的中间,也可能在它左边这一段里,或者右边的这一段里。在实现的时候我们可以根据二分法查找中间的元素,根据起始节点和中间节点的关系来判断左边这一段是一个单纯递增的段还是包含有另外一个递增段。然后根据中间节点和它前后的节点关系判断最小元素。
详细的实现如下:
public class Solution { public int findMin(int[] nums) { if(nums.length == 1) return nums[0]; if(nums[0] < nums[nums.length - 1]) return nums[0]; int l = 0, r = nums.length - 1, min = nums[0]; while(l < r) { int mid = (l + r) / 2; if(nums[l] <= nums[mid]) { if(nums[mid] > nums[mid + 1]) min = Math.min(min, nums[mid + 1]); l = mid + 1; } else { if(nums[mid] < nums[mid - 1]) min = Math.min(min, nums[mid]); r = mid - 1; } } return min; } }
相关推荐
leetcode 分类 :person_running::person_running::person_running: 算法 :person_running::person_running::person_running: 实践&理论 :books: :ear: :television: Binary Search(二分查找) easy 69: 278: 35: ...
leetcode写题闪退 #*的多少代表此题的有意思程度 有几题第一次写的时候思绪比较混乱: *****Regular Expression Matching 2014.10.29 对于Find Minimum in Rotated Sorted Array II 和 Find Minimum in Rotated ...
leetcode Coding-Interview A repo for popular coding interview problems mainly from Leetcode. 二分搜索/有序数组旋转 Find Minimum In Rotated Sorted Array Find Minimum In Rotated Sorted Array II Search ...
[Java](./src/Find minimum in Rotated Sorted Array II/Solution.java) 2014/10/20 难的 [Java](./src/在旋转排序数组中查找最小值/Solution.java) 2014/10/15 中等的 [Java](./src/最大乘积子阵列/Solution.java) ...
Find Minimum in Rotated Sorted Array viii. Largest Rectangle in Histogram ix. Maximal Rectangle x. Palindrome Number xi. Search a 2D Matrix xii. Search for a Range xiii. Search Insert Position xiv. ...
扔鸡蛋 leetcode LeetCode-Note-Mary Mary's leetcode notebook The order of problems ...in ...Minimum in Rotated Sorted Array(寻找旋转排序数组中的最小值) 2020/12/09 300. Longest Increasing
Leetcode扑克 项目简介 该项目为《剑指Offer》题解 OnlineJudge 题目 个人建议能使用LeetCode还是尽量用LeetCode。因为LeetCode题目接口更为规范,而且测试数据也更为全面。 牛客网 LeetCode 二维数组中的查找 240. ...
Find Minimum in Rotated Sorted Array II Median of Two Sorted Arrays H-Index II 暴力枚举法 Subsets Subsets II Permutations Permutations II Combinations Letter Combinations of a Phone Number 广度优先...
leetcode lintcode差异 leetcode-python 九章算法基础班 二分 题目 地址 153. Find Minimum in Rotated Sorted Array 双指针 题目 Solution Tag LintCode 604. Window Sum LeetCode 283. Moves Zeroes Array、Two ...
find-minimum-in-rotated-sorted-array-0153 数组的乘积-除了-self-0238 从排序数组中删除重复项-0026 搜索旋转排序数组-0033 两个整数之和-0371 二和-0001 回溯 组合-和-0039 组合总和-ii-0040 电话号码的字母组合 ...
leetcode变形词 :fire: Leetcode / 数据结构和算法 ...in_Rotated_Sorted_Array.java) :pushpin: 数组 :pushpin: 比赛 提交 2020 年 Google Code Jam 资格赛 提交 Google Hash Code 2020 在线资格赛
leetcode Phone interview: Implement hashmap Second minimum number in array given a sorted array, rotated at a pivot, find the maximum element what is encapsulation(封装) 大部分时间在问general ...