[分析] Find Minimum in Rotated Sorted Array是基础版,可用于打开基础思路,升级版是要考虑数组可能有重复元素。将题目中的case旋转多次找出思路,直接的思路是顺序遍历找到第一个非升序的元素,这种做法复杂度是O(N),优化的做法是每次通过比较中间元素和左边界元素来截掉一半元素。若nums[left] < nums[mid],说明左半边是升序,最小元素在右半边中,若nums[left] < nums[mid],说明最小元素在左半边,没有重复元素情况下每次总能截掉一半元素,因此复杂度是O(logN)。
有重复元素情况下,左右边界和中间元素均可能相等,这就导致我们无从判断最小元素在哪边,解决办法就是在这种情况下左边界移动一步直到和中间值不等或者相遇,最坏情况下为O(N).
不管是否有重复,如果当前考察的数组段nums[left-right],其nums[left] < nums[right]说明这段数组没有选中,nums[left]就是最小元素,一旦旋转nums[left] >= nums[right]。
循环只处理数组含三个元素以上的情况,若考察数组至多仅有两个元素,可比较确认最小元素。
重复元素处理思路参考Code Ganker博客,不理解他的实现中为什么需要维护min……
[ref]
http://blog.csdn.net/linhuanmars/article/details/40449299
public class Solution {
public int findMin(int[] nums) {
if (nums == null || nums.length == 0)
return 0;
int left = 0, right = nums.length - 1;
int mid = 0;
while (right - left > 1) {
if (nums[left] < nums[right])
return nums[left];
mid = left + (right - left) / 2;
if (nums[left] < nums[mid]) {
left = mid + 1;
} else if (nums[left] > nums[mid]){
right = mid;
} else {
left++;
}
}
return nums[left] < nums[right] ? nums[left] : nums[right];
}
}
分享到:
相关推荐
扔鸡蛋 leetcode LeetCode-Note-Mary Mary's leetcode notebook The order of problems ...in ...Minimum in Rotated Sorted Array(寻找旋转排序数组中的最小值) 2020/12/09 300. Longest Increasing
find-minimum-in-rotated-sorted-array-0153 数组的乘积-除了-self-0238 从排序数组中删除重复项-0026 搜索旋转排序数组-0033 两个整数之和-0371 二和-0001 回溯 组合-和-0039 组合总和-ii-0040 电话号码的字母组合 ...
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 ...
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 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 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扑克 项目简介 该项目为《剑指Offer》题解 OnlineJudge 题目 个人建议能使用LeetCode还是尽量用LeetCode。因为LeetCode题目接口更为规范,而且测试数据也更为全面。 牛客网 LeetCode 二维数组中的查找 240. ...
leetcode变形词 :fire: Leetcode / 数据结构和算法 ...in_Rotated_Sorted_Array.java) :pushpin: 数组 :pushpin: 比赛 提交 2020 年 Google Code Jam 资格赛 提交 Google Hash Code 2020 在线资格赛
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 广度优先...
[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) ...
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 ...