[LeetCode|[LeetCode 153] Find minimum in rotated sorted array (medium)
Solution 1
- Given it is a rotated array, then the left first half values are greater than the right later half values.
- Purpose: To find the
last position of the 1st half
andfirst position of 2nd half
- In order to do this, we need to keep
left pointer
always points to1st half
, andright pointer
always points to2nd half
- when
distance between left and right pointer == 1
, then we foundthe last position of the 1st half
andfirst position of 2nd half
; then the minimum one isthe first position of the 2nd half
- 求出middle,用nums [middle]与nums[end]比较
if (nums [middle] < nums[end]) {
end = middle;
} else if (nums [middle] > nums[end]) {
start = middle;
}
- 当
start + 1 == end
时,跳出循环。return Math.min (nums [start], nums[end]);
// iterative solution
class Solution {
public int findMin(int[] nums) {
int left = 0;
int right = nums.length - 1;
// purpose: to find the last element of subarray1 and first element of subarray2
// In order to do this, we need to keep left pointer always points to subarray1, and right poitner --> subarray2
// when distance between left and right is 1, then we found the last of subarray 1 and first of subarray2
// minimum is the first element of subarray2// this condition guarantee that it is rotated, if not then the first element is the mini
while (nums[left] > nums[right]) {
int middle = left + (right - left) / 2;
if (left + 1 == right) {
return nums[right];
}if (nums[middle] > nums[left]) {
// middle is inside subarray1, so move left to middle
left = middle;
} else {
// middle is inside subarray2, then move right to middle
right = middle;
}
}return nums[left];
}
}// recursion solution
class Solution {
public int findMin(int[] nums) {
int left = 0;
int right = nums.length - 1;
return findMin (nums, left, right);
}public int findMin (int[] nums, int left, int right) {
if (nums[left] < nums[right]) {
return nums[left];
}if (left + 1 >= right) {
return Math.min (nums[left], nums[right]);
}int middle = left + (right - left) / 2;
int min1 = findMin (nums, left, middle);
int min2 = findMin (nums, middle + 1, right);
return Math.min (min1, min2);
}}
Code2
class Solution {
public int findMin(int[] nums) {
if (nums == null || nums.length == 0)
return 0;
int start = 0;
int end = nums.length - 1;
while (start + 1 < end) {
int middle = start + (end - start) / 2;
if (nums [middle] < nums[end]) {
end = middle;
} else if (nums [middle] > nums[end]) {
start = middle;
}
}return Math.min (nums [start], nums[end]);
}
}
推荐阅读
- 【Leetcode/Python】001-Two|【Leetcode/Python】001-Two Sum
- leetcode|leetcode 92. 反转链表 II
- 二叉树路径节点关键值和等于目标值(LeetCode--112&LeetCode--113)
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器(Swift)
- LeetCode(03)Longest|LeetCode(03)Longest Substring Without Repeating Characters
- Leetcode|Leetcode No.198打家劫舍
- [leetcode数组系列]1两数之和
- 运行报错Cannot|运行报错Cannot find module '@babel/compat-data/corejs3-shipped-proposals’
- CBB1007
- 数据结构和算法|LeetCode 的正确使用方式