查看: 5117|回复: 31
收起左侧

Amazon : Find a[i] == i

|只看干货 |刷题
头像被屏蔽

分享帖子到朋友圈
wwwyhx | 显示全部楼层 |阅读模式
提示: 作者被禁止或删除 内容自动屏蔽

上一篇:Microsoft : Rearrange an array of positive and negative integers,
下一篇:Facebook : 构造递减数列
bignews 2011-6-11 13:58:22 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (233)
 
 
1% (4)    👎
bool found = false;
for (i=0; i < LEN && S[i] < LEN; i++)
{
    if (S[i] == i)
    {
        printf("%d\n", i);
        found = true;
    }
}
if (!found)
    printf("-1\n");

O(n)的。。。有优化算法吗?
回复

使用道具 举报

198896px 2012-2-16 16:57:28 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   95% (20)
 
 
4% (1)    👎
public static int find(int[] array, int start, int end){
     int mid = (start+end)/2;
     if(array[mid]==mid){
          return mid;
     }
     else if(array[mid] > mid){
          return find(array, start, mid-1);
     }
     else if(array[mid] < mid){
          return find(array, mid+1,end);
     }
}

log(n)
回复

使用道具 举报

playboylc 2012-2-17 07:01:57 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (86)
 
 
2% (2)    👎
最基础的递归找中值题,应该是nlgn
回复

使用道具 举报

198896px 2012-2-17 11:48:04 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   95% (20)
 
 
4% (1)    👎
nlogn的话还不如遍历呢。。
回复

使用道具 举报

tsy3602 2012-2-18 00:14:22 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (79)
 
 
2% (2)    👎
本帖最后由 tsy3602 于 2012-2-18 00:17 编辑

回复 3# 198896px

这个做法不太对吧,有个问题,比如说有相等元素的情况
比如 1,2,3,5,5,5这个数组,
最初,
start =0 , end =5
然后 array[2] = 3,你直接往前找了,结果就没找到,事实上,array[5]=5,是存在的,另外,你没有在没查到的情况返回-1.
回复

使用道具 举报

diamrem 2012-2-18 04:52:46 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (285)
 
 
1% (4)    👎
如果原数组是严格递增的,可以用binary search。

如果不是的话,是不是只有遍历了?
回复

使用道具 举报

198896px 2012-2-18 07:13:17 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   95% (20)
 
 
4% (1)    👎
回复 6# tsy3602


    没写返回-1是我不想写。。。
按你举的例子,可以左右都扫,左边扫12,右边从第三个5开始扫,因为前两个5和他们的index比起来小,所以可以忽略,那这样的话,递归下去,按value和index比较来缩小范围,还是比遍历好,因为可以少扫不少元素。
回复

使用道具 举报

198896px 2012-2-18 07:18:22 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   95% (20)
 
 
4% (1)    👎
改进如下:

int midindex = (start+end)/2;
int midvalue = array[midindex];
...

int leftindex = MIN(midindex-1,midvalue);
int left = find(array,start,leftindex);
if(left > 0){
   return left;
}

int rightindex = MAX(midIndex+1,midvalue);
int right = find(array,rightindex,end);
return right;
}
回复

使用道具 举报

ilovexiao77 2012-2-27 00:37:31 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   96% (25)
 
 
3% (1)    👎
果断二分搜索啊~
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■拉群请前往同学同事飞友|拉群结伴版块,其他版块拉群,帖子会被自动删除
■论坛不能删帖,为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://tools.1point3acres.com/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

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