LeetCode153——寻找旋转排序数组中的最小值
我的LeetCode代码仓:https://github.com/617076674/LeetCode
原题链接:https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/description/
题目描述:
知识点:二分查找法
思路一:暴力**法
直接遍历一遍整个数组,寻找最小值。
时间复杂度是O(n),其中n为数组中的元素个数。空间复杂度是O(1)。
JAVA代码:
public class Solution {
public int findMin(int[] nums) {
int result = Integer.MAX_VALUE;
for (int i = 0; i < nums.length; i++) {
if(nums[i] < result){
result = nums[i];
}
}
return result;
}
}
LeetCode解题报告:
思路二:二分查找法
思路一并没有把排序数组这个特性利用起来,我们用二分查找法来利用数组有序这个特性。
时间复杂度是O(logn),其中n为数组中的元素个数。空间复杂度是O(1)。
JAVA代码:
public class Solution {
public int findMin(int[] nums) {
int left = 0, right = nums.length - 1;
while (left < right) {
if (right - left == 1) {
return Math.min(nums[left], nums[right]);
}
int mid = left + (right - left) / 2;
if (nums[left] < nums[right]) {
return nums[left];
} else {
if (nums[left] < nums[mid]) {
left = mid;
} else {
right = mid;
}
}
}
return nums[left];
}
}
LeetCode解题报告: