一道面试题


题目: 有一个长度是101的数组,存有1 ~ 100这100个数字,其中一个是重复的。请设计一个算法找出这个重复的数字

 
#!/usr/bin/env python
#-*- coding:utf-8 -*-

arr1 = [5,2,1,9,6,2,8]
arr2 = {}.fromkeys(arr1).keys()
print arr2
#效率高,但不符合题目要求

arr3 = list(set(arr1))
print arr3
#效率更高,但仍然不符合题目要求

arr4 = sorted(arr1)
i = len(arr4) - 1
for x in range(i):
    y = x + 1
    if arr4[x] == arr4[y]:
        print arr4[x]
#达到题目要求了,可惜面试时间已过
#当时怎么就没有想到用sorted这个方法呢
#还是自己技术太差了
#惭愧啊惭愧

有哪位前辈有效率更高的算法,还请告诉我这个菜鸟,谢谢。

  1. #1 by 刀尖红叶 on 2014/02/15 - 22:34

    前辈不敢当,您才是我前辈~
    我自己想了个算法测试了下略快:
    http://leafonsword.org/yi-dao-pythonmian-shi-ti/

    • #2 by mcsrainbow on 2014/02/15 - 23:35

      很不错的思路啊,利用去重后的list与原有的list进行求和取差值。
      比傻傻的用for循环好。

      • #3 by 刀尖红叶 on 2014/02/16 - 10:56

        希望博客加个回复邮件提醒功能,要不是打开这页面我都不知道你的回复~

  2. #4 by vistamin on 2014/02/16 - 11:42

    直接把这101个数字加起来,然后减去5050,就是那个重复的数字。
    比如1,2,2,3,这4个数字,加起来是8,然后减去1+2+3,最后结果是2.那么2就是重复的。

    • #5 by sender on 2014/02/21 - 17:57

      对。题目已经限定得很清楚了。考的就是读题能力。

  3. #6 by itchanges on 2014/02/19 - 01:53

    public static int process(int[] data){
    int[] a = new int[data.length-1];
    for(int i=0;i<data.length;i++){
    if(a[data[i]]==1)
    return data[i];
    else
    a[data[i]] =1;
    }
    return -1;
    }

    public static void processTest(){
    int[] arr1= {0,1,1,2};
    int[] arr2= {0,1,2,3,3,4,5};
    System.out.println(process(arr1));
    System.out.println(process(arr2));
    }

  4. #7 by guest on 2014/02/20 - 07:25

    why so complicated?

    $ cat t
    5,2,1,9,6,2,8
    $ cut -d',' --output-delimiter=' ' -f1- < t | tr ' ' '\n' | sort | uniq -c | awk '!/ 1 / {print $2}'
    2

  5. #8 by 陈奇 on 2014/03/24 - 20:44

    1、不编程的方法:
    sum(arr1) - 5050
    /*sum(range(1,101)) + repeate_num*/

    2、python实现:
    import collections
    collections.Counter(arr1).most_common(1)[0][0]

  6. #9 by cyrus on 2014/04/10 - 12:48

    #!py
    arr1 = [5,2,1,9,6,2,8]
    [i for i in arr1 if arr1.count(i) == 2]
    result: [2, 2]

  7. #10 by tony on 2014/05/05 - 13:58

    取和后-5050

  8. #11 by xuzhigui on 2014/07/09 - 16:43

    也可以这么来实现:

    #!/usr/bin/env python
    import collections
    arr1 = [5,2,1,9,6,2,8]
    Count2 = collections.Counter(arr1)
    for k,v in Count2.most_common():
    if v != 1:
    print k

  9. #12 by liluo on 2014/08/04 - 00:36

    n = 100
    for i in range(1, 101):
    n ^= i

    print n

(will not be published)
*