首页 > 代码库 > Find Minimum in Rotated Sorted Array II
Find Minimum in Rotated Sorted Array II
The worst situation O(N).
Actually we can either just loop through, or we can compare num[mid] with the num[end], if they are the same, that means it‘s fine to remove end, the smallest element won‘t be removed
public class Solution { /** * @param num: a rotated sorted array * @return: the minimum number in the array */ public int findMin(int[] num) { // write your code here if (num == null || num.length == 0) { return -1; } int start = 0; int end = num.length - 1; while (start + 1 < end) { int mid = start + (end - start) / 2; // we want to keep the lower part, so use endVal to compare if (num[mid] == num[end]) { end--; } else if (num[mid] < num[end]) { end = mid; } else { start = mid; } } if (num[start] <= num[end]) { return num[start]; } if (num[end] < num[start]) { return num[end]; } return -1; } }
Find Minimum in Rotated Sorted Array II
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。