leetcode又出新题了

Find Minimum in Rotated Sorted Array II. 就是Find Minimum in Rotated Sorted Array中有重复的数怎么办。
https://oj.leetcode.com/problems ... ed-sorted-array-ii/
比较烦的是如果
num[mid] = num[start] = num[end]
怎么办。
这种情况下我就
start = start + 1;
if(num[start] < num[end]){
        return num[start];
}
了。
不知道大家有没有啥更好的想法。
我的代码：

您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

[url=https://oj.leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/][/url]

public class Solution {
    public int findMin(int[] num) {
        int i = 0;
        int j = num.length - 1;
        while (i + 1 < j) {
            int mid = i + (j - i) / 2;
            if (num[mid] > num[j]) {
                i = mid;
            }
            else if (num[mid] < num[j]){
                j = mid;
            }
            else {
                j--;
            }
        }
        return Math.min(num[i], num[j]);
    }
}

大家都在贴代码，那我也来贴好了~
worst也是o(n)
只要不要数字都一样 还是logn可以搞定哒！

1. public class Solution {
   
2.     public int findMin(int[] num) {
   
3.         if (num.length <=1) return num[0];
   
4.         int low=0, high=num.length -1, mid;
   
5.         while (low < high) {
   
6.             mid = (low + high)/2;
   
7.             while ((num[low] == num[mid]) && num[mid]== num[high]) {
   
8.                 low++; high--;
   
9.                 if (low >=high) break;
   
10.             }
    
11.             if (num[low] <= num[mid]) {
    
12.                 if (num[mid] <= num[high]) high = mid;
    
13.                 else low = mid +1;
    
14.             }
    
15.             else high = mid;
    
16.         }
    
17.         return num[low];
    
18.     }
    
19. }

复制代码

感觉这种worst case是O(n)的。。。class Solution {
public:
    // actually we are finding the pivot
    int findMin(vector<int> &num) {
        assert(!num.empty());
        return findMin(num, 0, num.size() -1);
    }
    int findMin(vector<int> &num, int start, int end) {
        if (start >= end)
            return num[start];
        int mid = start + (end - start) / 2;
        if (num[mid] < num[end])
            findMin(num, start, mid);
        else if (num[mid] == num[end]) {
            return min(findMin(num, start, mid), findMin(num, mid+1, end));
        }
        else
            findMin(num, mid+1, end);
    }
};

cqx83 发表于 2014-10-22 07:12
public class Solution {
    public int findMin(int[] num) {
        int i = 0;

嗯，是比我的想法好！

415044809 发表于 2014-10-21 15:15
嗯，是比我的想法好！

其实思路基本一样的～

其实不用二叉，直接遍历也能过。。。

xcf1992 发表于 2014-10-21 16:03
其实不用二叉，直接遍历也能过。。。

面试的时候直接遍历就挂了。。。

leetcode又出新题了

让不让人活了…