问题描述:
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.
原问题链接:https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/
问题分析
这个问题和前一个有点不一样的地方在于,它允许里面有重复的元素。这样它里面的情况就稍微有点不一样了。我们还是可以通过原来的方式判断当前段是在哪个部分,只是判断的条件稍微有点变化。这里还存在一种左边的值和中间节点值相等的情况。也可能在数组中间两边节点的值也是相等的。
在实现的时候,我们如果发现左边节点值比中间节点值小,说明它是在左边的上升段上,那么这和原来的设定是一样,l = mid + 1。我们取的最小值就不能去看mid后面的值了,而是判断l和min之间更小的那个值。同样对于右边节点值也适用。
详细的代码实现如下:
public class Solution { public int findMin(int[] nums) { if(nums.length == 1) return nums[0]; int l = 0, r = nums.length - 1, min = nums[0]; while(l < r - 1) { int mid = (l + r) / 2; if(nums[l] < nums[mid]) { min = Math.min(min, nums[l]); l = mid + 1; } else if(nums[l] > nums[mid]) { min = Math.min(min, nums[mid]); r = mid - 1; } else l++; } min = Math.min(min, Math.min(nums[l], nums[r])); 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
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扑克 项目简介 该项目为《剑指Offer》题解 OnlineJudge 题目 个人建议能使用LeetCode还是尽量用LeetCode。因为LeetCode题目接口更为规范,而且测试数据也更为全面。 牛客网 LeetCode 二维数组中的查找 240. ...
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 ...