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

Microsoft : Find missing number in a sorted array

全局:

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
一个sorted interger Array[1...N], 已知范围 1...N+1. 已知一个数字missing。
找该数字。

就这么简单,程序一次写对哈

上一篇:facebook : Print the largest number within a moving window
下一篇:Google/Microsoft : Brain test
🔗
 楼主| wwwyhx 2011-8-21 12:05:46 | 只看该作者
全局:
DA-TA
往左边的时候要注意上界包含中间值

  1. int GetMissing(int A[], int n)
  2. {
  3.         assert(A && n > 0);

  4.         int nBeg = 0;
  5.         int nEnd = n-1;
  6.         while (nBeg < nEnd)
  7.         {
  8.                 int nMid = (nBeg + nEnd)/2;
  9.                 if (A[nMid] != nMid + 1)
  10.                         nEnd = nMid;
  11.                 else
  12.                         nBeg = nMid + 1;
  13.         }

  14.         return A[nEnd];
  15. }
复制代码
回复

使用道具 举报

🔗
iveney 2011-8-24 09:58:33 | 只看该作者
全局:
本帖最后由 iveney 于 2011-8-24 10:00 编辑

直接遍歷 O(n).
因爲是 sorted 的, 並且是 1 .. N+1
所以只需要找到第一個數的下標不是它本身即可.

Example:

  1. Index: 1 2 3 4 5
  2. value: 1 2 3 5 6
复制代码

推广一下, 範圍可以是 K .. K+1, 只需在比較時加上相應的 shift 即可.
回复

使用道具 举报

🔗
 楼主| wwwyhx 2011-8-24 10:12:00 | 只看该作者
全局:
直接遍歷 O(n).
因爲是 sorted 的, 並且是 1 .. N+1
所以只需要找到第一個數的下標不是它本身即可.

Example:
推广一下, 範圍可以是 K .. K+1, 只需在比較時加上相應的 shift 即可.
iveney 发表于 2011-8-24 09:58


用二分可以做到log(n)
回复

使用道具 举报

🔗
iveney 2011-8-24 22:54:55 | 只看该作者
全局:
讚, 疏忽了. 二分本質上是跟我的 idea 一樣的.
回复

使用道具 举报

🔗
zt7584 2013-8-26 20:43:20 | 只看该作者
全局:
wwwyhx 发表于 2011-8-20 23:05
DA-TA
往左边的时候要注意上界包含中间值

感觉如果是找missing的number,那这个number应该就不在这个数组里面吧,那为什么楼主要返回A[bla..bla...]?

根据楼主的思路,应该返回nEnd+1,才是missing的那个number。
回复

使用道具 举报

🔗
eli 2013-8-27 16:18:50 | 只看该作者
全局:
那么数组里会不会有重复呢0 0
回复

使用道具 举报

🔗
guchang 2013-8-29 15:11:50 | 只看该作者
全局:
lz,为何你题目前都加巨硬呢????
回复

使用道具 举报

🔗
aerolite 2013-11-4 09:19:45 | 只看该作者
全局:
本帖最后由 aerolite 于 2013-11-4 09:21 编辑

#include <iostream>
using namespace std;
#include <vector>
#include <assert.h>

int getMissing(int arr[], int n){
    int low=0;
    int high=n-1;
    int mid;
    while(low<high){
        mid=(low+high)/2;
        if(arr[mid]==mid){
            low=mid;
        }
        else{
            high=mid;
        }
        if(high-low==1) break;
    }
    if(arr[low]!=low&&arr[high]!=high) return arr[low]-1;
    if(arr[low]==low&&arr[high]==high) return arr[high]+1;
    else return arr[low]+1;
}

int main(){
    int arr[]={0, 1, 3};
    int result=getMissing(arr, 3);
    cout<<result;
}

回复

使用道具 举报

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

本版积分规则

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