📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
楼主: tanpf5
跳转到指定楼层
上一主题 下一主题
收起左侧

[二分/排序/搜索] 问一个关于binary search循环跳出条件的问题

🔗
G_cy 2016-1-4 12:29:01 | 只看该作者
全局:
嗯,上面那个说一直用low+1< high的也不错,反正出来是两个值做一次比较就能知道哪个是结果,不容易搞混挺好的
回复

使用道具 举报

🔗
163 2016-1-4 15:30:11 | 只看该作者
全局:
闲庭听雨 发表于 2016-1-4 08:41
受益匪浅!大神!
那请问一下对于Search the turing point in a rotated array或者是search the min val ...

给,你要的 +-1版的 findMin

class Solution {
public:
    int findMin(vector<int>& nums) {
        if (nums.size() == 1) {
            return nums[0];
        }
        int left = 1;
        int right = nums.size() - 1;
        int mid;
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (nums[mid] <= nums[0]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        if (left == nums.size()) {
            return nums[0];
        } else {
            return nums[left];
        }
    }
};

最后一个判断其实可以改成 return nums[left % nums.size()];
当left == nums.size()时,其实就对应我前面说的 out of bounds的情形,但是因为这里是rotation array,所以实际上是转了个圈,index n 其实就是 index 0
回复

使用道具 举报

🔗
163 2016-1-4 15:37:11 | 只看该作者
全局:
本帖最后由 163 于 2016-1-4 15:40 编辑
jigsaw_Becky 发表于 2016-1-4 09:39
你好,除了ls那个turning point in a rotated array,我也还有个类似的问题leetcode 268 missing number
...

首先你这个code是错的,此题要求O(n)time,所以先sort就已经不符合要求了。不过你如果sort了,
那么就是求 “第一个满足nums.at(i) > i" 的index,这个用+- 1的方法毫无问题, code 如下:

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        int left = 0;
        int right = n - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > mid) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
};

提交已过,请自行琢磨细节。
另外对于此题,还是请先想想O(n)怎么解

评分

参与人数 1大米 +5 收起 理由
jigsaw_Becky + 5 感谢分享!

查看全部评分

回复

使用道具 举报

🔗
163 2016-1-4 15:38:25 | 只看该作者
全局:
闲庭听雨 发表于 2016-1-4 09:43
你的这个题可以用XOR位运算做。。复杂度只需要O(N)你现在这个先排序要慢点。。

位运算怎么做?你做做试试。。。
回复

使用道具 举报

🔗
163 2016-1-4 15:45:14 | 只看该作者
全局:
jigsaw_Becky 发表于 2016-1-4 09:39
你好,除了ls那个turning point in a rotated array,我也还有个类似的问题leetcode 268 missing number
...

给你bia个最好理解的O(n)的做法

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int sum = 0;
        for (int a : nums) {
            sum += a;
        }
        int n = nums.size();
        return n * (n + 1) / 2 - sum;
    }
};

评分

参与人数 1大米 +5 收起 理由
jigsaw_Becky + 5 感谢分享!

查看全部评分

回复

使用道具 举报

🔗
Mr_DwZ 2016-1-4 16:12:30 | 只看该作者
全局:
把区间表示统一就好了呀~
比如你在整个二分查找里边界表示是 [x, y),结果边界一样是[x, y)的形式。
比如最后结果是找一个数,这样的区间就是 [left, left+1)。这样一想就很好判断了!
回复

使用道具 举报

🔗
jigsaw_Becky 2016-1-4 21:01:47 | 只看该作者
全局:
163 发表于 2016-1-4 15:37
首先你这个code是错的,此题要求O(n)time,所以先sort就已经不符合要求了。不过你如果sort了,
那么就是 ...

十分感谢你的回答!
回复

使用道具 举报

🔗
jigsaw_Becky 2016-1-4 21:19:19 | 只看该作者
全局:
本帖最后由 jigsaw_Becky 于 2016-1-4 21:21 编辑
163 发表于 2016-1-4 15:38
位运算怎么做?你做做试试。。。

这样的~~也是看的别人的方法~~
public int missingNumber(int[] nums) {
        //方法一.异或XOR
        //把数组以及0~nums.length拿来异或。这样每个0~n的数就应该出现两次了,除了目标结果(只出现了一次)。出现2次的数就异或没有了,剩下的就是出现一次的数。
        //参考:http://www.jiarui-blog.com/2015/ ... 268-missing-number/              
int result=nums.length;
        for(int i=0;i<nums.length;i++){
            result^=i;
            result^=nums;
        }
        return result;
}




回复

使用道具 举报

🔗
 楼主| tanpf5 2016-1-4 21:55:12 | 只看该作者
全局:
Mr_DwZ 发表于 2016-1-4 16:12
把区间表示统一就好了呀~
比如你在整个二分查找里边界表示是 [x, y),结果边界一样是[x, y)的形式。
比如 ...

具体讲讲?
回复

使用道具 举报

🔗
163 2016-1-4 22:05:33 | 只看该作者
全局:
本帖最后由 163 于 2016-1-4 22:06 编辑
jigsaw_Becky 发表于 2016-1-4 21:19
这样的~~也是看的别人的方法~~
public int missingNumber(int[] nums) {
        //方法一.异或XOR

有道理
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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