登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

银河里的星星

落在人间

 
 
 

日志

 
 

万里挑一  

2008-06-22 12:17:03|  分类: 思维训练 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

一个整形数组,长为n,元素范围为1~(n-1),则这个数组内至少有一个数字出现多次,现在要求用O(n)时间,O(1)空间找出一个出现多次的数。
以下为原文:
here's one I got asked which kicked my butt.  Write a function that takes in an array of n ints from 1...n-1.  For example, an array of 4 numbers which all have values of 1, 2, or 3.  There will obviously be at least one duplicate number.  Return one of the duplicates (EASY!) - Now do this in order n, without allocating ANY new memory (no hash table or anything).. (Note: I did figure out a solution to this, but the interview didn't seem to like it very much but whatever)..

---------------------------------------------------------------------------------------------------------------------------------------------

answer:

如果允许修改数组,可以利用置换监测,二分也可以做到
如果不允许,可以利用冗余位,变反标记,然后恢复,不过这样本质上的空间不是O(1),虽然ms是O(1)

如n=100,数的范围是1-99,重复的为23
置换监测:
假设把23换成100,则刚好形成一个置换,这样数字刚好构成一些轮换
反过来说刚好是100换成了23造成了一个环的断裂,这样就可以根据能否构成轮换来判断,而发生分叉的地方刚好就是23。
出现如下典型的结构,置s[i] = -1; 然后置s[s[i]],s[s[s[i]]]...
代码大体如下:
#include <stdio.h>
int main(int argc, char *argv[])
{

    int i,t,n = 5,temp,head;
    int s[6] = {0,1,2,3,4,1,};
    for(i = 1 ; i <= n ; i++){
        if(s[i] == -1)
            continue;
        head = temp = i;
        while(s[temp] != -1){
            t = s[temp];
            s[temp] = -1;
            temp = t;
        }
        if(temp != head)
            return  printf("%d\n",temp);

    }
    printf("ok\n");
    return 0;
}

二分:
数的范围是1-99,以中间值50划分,如无重复,>=50的本应当有50个,<50的本应当有49个,计数发现小于50的有50个,则说明肯定是<50的那部分中有一个重复的,这样就可以减半。以50为中间元进行划分是O(n)的,划分的同时可以计数。二分减半,总的复杂度为O(n)。

利用冗余位,是指在置换监测中,不是让s[i] = -1,而是 s[i] = - s[i],这样监测完,再让s[i] = -s[i],就恢复原值了,表面上没有增加空间,实际上还是利用了一个冗余的符号位。

  评论这张
 
阅读(508)| 评论(3)

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018