Find Minimum in Rotated Sorted Array -- LeetCode
LeetCode -- in Array Find sorted minimum rotated
2023-09-11 14:14:10 时间
这道题是Search in Rotated Sorted Array的扩展,差别就是如今不是找一个目标值了,而是在bst中找最小的元素。主要思路还是跟Search in Rotated Sorted Array差点儿相同。还是通过左边界和中间的大小关系来得到左边或者右边有序的信息。假设左半边有序。那么左半边最小就是左边第一个元素,能够和当前最小相比取小的,然后走向右半边。否则,那么就是右半半边第一个元素,然后走向左半边。这样子每次能够截掉一半元素,所以最后复杂度等价于一个二分查找。是O(logn),空间上仅仅有四个变量维护二分和结果,所以是O(1)。代码例如以下:
public int findMin(int[] num) { if(num == null || num.length==0) return 0; int l = 0; int r = num.length-1; int min = num[0]; while(l<r-1) { int m = (l+r)/2; if(num[l]<num[m]) { min = Math.min(num[l],min); l = m+1; } else if(num[l]>num[m]) { min = Math.min(num[m],min); r = m-1; } else { l++; } } min = Math.min(num[r],min); min = Math.min(num[l],min); return min; }有朋友可能注意到上面的实现还有第三种情况,就是左边界和中间是相等的情况。这道题目事实上是不用发生的,由于元素没有反复。而Find Minimum in Rotated Sorted Array II这道题这考虑了元素反复的情况,这里仅仅是为了算法更加一般性。就把那个情况也包括进来,有兴趣的朋友能够看看Find Minimum in Rotated Sorted Array II对反复元素的分析哈。
相关文章
- leetcode 之Sum系列(七)
- Java实现 LeetCode 710 黑名单中的随机数(黑白名单)
- Java实现 LeetCode 671 二叉树中第二小的节点(遍历树)
- Java实现 LeetCode 1两数之和
- Java实现 LeetCode 290 单词规律
- Java实现 LeetCode 100 相同的树
- Java实现 LeetCode_0048_RotateImage
- LeetCode(23):合并K个排序链表
- [LeetCode] Single Number III
- 【二叉树】LeetCode 94. 二叉树的中序遍历【简单】
- Leetcode学习计划之动态规划入门day13(931,120)
- leetcode 518. 零钱兑换 II-----完全背包套路模板
- 【LeetCode Python实现】43. 字符串相乘(中等)
- Leetcode 152. 乘积最大子数组(暴力破解居然可以通过!)
- [LeetCode] 46. Int数组全排列 ☆☆☆(回溯)
- leetcode 54. 螺旋矩阵 js高效实现
- leetcode 17 -- Letter Combinations of a Phone Number
- Leetcode--Add Two Numbers
- [leetcode]Next Permutation
- 力扣LeetCode,前 K 个高频元素
- 【Leetcode刷题Python】 LeetCode 2038. 如果相邻两个颜色均相同则删除当前颜色
- LeetCode 1206. 设计跳表
- LeetCode 82. 删除排序链表中的重复元素 II