Follow up for "Find Minimum in Rotated Sorted Array":
What if duplicates are allowed?Would this affect the run-time complexity? How and why?
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.
The array may contain duplicates.
Solution 1:
public int findMin(int[] num) { int start = 0, end = num.length - 1; int min = num[0]; while(start < end-1) { int mid = (start + end) / 2; if(num[start] < num[mid]) { min = Math.min(min, num[start]); start = mid + 1; } else if(num[start] > num[mid]) { min = Math.min(min, num[mid]); end = mid - 1; } else { start++; } } min = Math.min(min, Math.min(num[start], num[end])); return min; }
Solutoin 2:
这是一个更加简单易懂的版本。
public int findMin(int[] num) { int l = 0, h = num.length-1; while(l < h && num[l] >= num[h]) { int m = (l + h) / 2; if(num[m] > num[h]) { // 4 5 6 7 0 1 2, min位于左侧上升沿与右侧上升沿之间 l = m + 1; } else if(num[m] < num[h]) { // 7 0 1 2 4 5 6, min位于上升沿左侧 h = m; } else { // num[m] == num[h] l++; } } return num[l]; }
图解一下数组可能出现的情况:
相关推荐
leetcode 分类 :person_running::person_running::person_running: 算法 :person_running::person_running::person_running: 实践&理论 :books: :ear: :television: Binary Search(二分查找) easy 69: 278: 35: ...
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 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写题闪退 #*的多少代表此题的有意思程度 有几题第一次写的时候思绪比较混乱: *****Regular Expression Matching 2014.10.29 对于Find Minimum in Rotated Sorted Array II 和 Find Minimum in Rotated ...
Leetcode扑克 项目简介 该项目为《剑指Offer》题解 OnlineJudge 题目 个人建议能使用LeetCode还是尽量用LeetCode。因为LeetCode题目接口更为规范,而且测试数据也更为全面。 牛客网 LeetCode 二维数组中的查找 240. ...
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 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 II Median of Two Sorted Arrays H-Index II 暴力枚举法 Subsets Subsets II Permutations Permutations II Combinations Letter Combinations of a Phone Number 广度优先...
leetcode变形词 :fire: Leetcode / 数据结构和算法 ...in_Rotated_Sorted_Array.java) :pushpin: 数组 :pushpin: 比赛 提交 2020 年 Google Code Jam 资格赛 提交 Google Hash Code 2020 在线资格赛
[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 ...