思维训练

万里挑一

2008年6月22日 阅读(16)

一个整形数组,长为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],就恢复原值了,表面上没有增加空间,实际上还是利用了一个冗余的符号位。

You Might Also Like

No Comments

Leave a Reply