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

Amazon : Find a[i] == i

🔗
mithril 2012-2-29 11:26:04 | 只看该作者
全局:
显然二分搜索比较快,写一遍=。=
回复

使用道具 举报

🔗
kinslover 2012-2-29 14:24:37 | 只看该作者
全局:
mid = (left+right)/2
If(a[mid]==mid) return mid
Else if a[mid] <mid xxxxx
Else. Xxxxxx
回复

使用道具 举报

🔗
searinox 2012-3-4 05:53:12 | 只看该作者
全局:
回复 8# 198896px

这个例子没必要递归二分吧,midvalue和midindex大小根本无法决定result在左在右,performance起码是O(n)

    public static int find(int[] array){
        int cur_index = 0;
        while(cur_index<array.length){
            if(cur_index == array[cur_index])
                return cur_index;
            else
                cur_index = Math.max(cur_index+1, array[cur_index]);
        }
        return -1;
    }
回复

使用道具 举报

🔗
198896px 2012-3-6 02:19:48 | 只看该作者
全局:
回复 13# searinox


    看9楼。
回复

使用道具 举报

🔗
searinox 2012-3-6 02:37:41 | 只看该作者
全局:
回复 14# 198896px

你这个也是O(n)的
回复

使用道具 举报

🔗
198896px 2012-3-6 14:39:51 | 只看该作者
全局:
回复 15# searinox


   最坏当然是O(n),但是平均可以到logn. 因为可以少扫描一些元素。
回复

使用道具 举报

🔗
wynnzh 2012-3-21 22:34:10 | 只看该作者
全局:
回复 16# 198896px


    如果出现多个相等怎么办?
回复

使用道具 举报

🔗
wynnzh 2012-3-21 23:00:33 | 只看该作者
全局:
回复 13# searinox


    顶!跟我想的一样。另外,二分查找的方法是不对的。对于a[i]>i的情况,也应该看左侧分支有没有相等出现。
回复

使用道具 举报

🔗
wynnzh 2012-3-21 23:23:25 | 只看该作者
全局:
回复 13# searinox


    顶!跟我想的一样。另外,二分查找的方法是不对的。对于a[i]>i的情况,也应该看左侧分支有没有相等出现。
    但是为了找到全部解,不能return吧。。应该print。
java......

   String find( int[] a){
      int i=0;
      StringBuilder j;//把位置结果存在String 中。也可以存在数组,arraylist,set。。。。what ever。
      while (i<a.length){
         if(a[i]==i)   {
             j.append(i.toString()).append(" ");
             i++;
         }
         else
            i=Math.max(i+1, a[i]);
       }
       return j;
    }
回复

使用道具 举报

🔗
parker0203 2012-3-22 12:52:39 | 只看该作者
全局:
回复 18# wynnzh


    同意这个看法,二分搜索在这边行不通,还不如遍历,
如果二分搜索找到合适的就直接return,那么遍历也可以照样找到合适的就直接return
这样还是遍历快些
回复

使用道具 举报

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

本版积分规则

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