一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1392|回复: 13
收起左侧

[Leetcode] leetcode又出新题了

[复制链接] |试试Instant~ |关注本帖
415044809 发表于 2014-10-22 06:59:27 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 415044809 于 2014-10-22 07:01 编辑

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];
}
了。
不知道大家有没有啥更好的想法。
我的代码:
游客,如果您要查看本帖隐藏内容请回复


[url=https://oj.leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/][/url]
cqx83 发表于 2014-10-22 07:12:55 | 显示全部楼层
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]);
    }
}

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

 楼主| 415044809 发表于 2014-10-22 07:15:49 | 显示全部楼层
cqx83 发表于 2014-10-22 07:12
public class Solution {
    public int findMin(int[] num) {
        int i = 0;

嗯,是比我的想法好!
回复 支持 反对

使用道具 举报

cqx83 发表于 2014-10-22 07:57:10 | 显示全部楼层
415044809 发表于 2014-10-21 15:15
嗯,是比我的想法好!

其实思路基本一样的~
回复 支持 反对

使用道具 举报

xcf1992 发表于 2014-10-22 08:03:30 | 显示全部楼层
其实不用二叉,直接遍历也能过。。。
回复 支持 反对

使用道具 举报

cqx83 发表于 2014-10-22 08:05:46 | 显示全部楼层
xcf1992 发表于 2014-10-21 16:03
其实不用二叉,直接遍历也能过。。。

面试的时候直接遍历就挂了。。。
回复 支持 反对

使用道具 举报

U.S.A 发表于 2014-10-22 08:33:43 | 显示全部楼层
leetcode又出新题了
回复 支持 反对

使用道具 举报

孤笑客 发表于 2014-10-22 10:10:39 | 显示全部楼层
让不让人活了…
回复 支持 反对

使用道具 举报

王可雪 发表于 2014-10-22 10:40:35 | 显示全部楼层
本帖最后由 王可雪 于 2014-10-22 10:44 编辑

感觉这种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);
    }
};


回复 支持 反对

使用道具 举报

jaly50 发表于 2014-10-22 11:50:39 | 显示全部楼层
大家都在贴代码,那我也来贴好了~
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. }
复制代码

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

kaito666k 发表于 2014-10-27 15:55:39 | 显示全部楼层
@10

binary 看着很正解阿
回复 支持 反对

使用道具 举报

Frankhappens 发表于 2014-10-28 00:58:19 | 显示全部楼层
我也是这么做的
回复 支持 反对

使用道具 举报

smzfeng 发表于 2014-10-28 03:18:03 | 显示全部楼层

原来阿Tang哥也在关注刷题
回复 支持 反对

使用道具 举报

孤笑客 发表于 2014-10-28 09:29:55 | 显示全部楼层
smzfeng 发表于 2014-10-28 03:18
原来阿Tang哥也在关注刷题

给你发现了,哈哈哈
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-7 04:12

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表