从一百个数中找不存在的数

发仔很忙

碰到个面试题目，有一百个1到100的数字，为乱序的，其中缺一个数字，简述用什么方法能够最快速的查找出缺的那个数字，以及循环多少次？大家有什么好的解法？

sqfasd

假设重复的是X，缺的是Y，假设数组为a1,a2....a100,和为S
X-Y = S - 5050
X^Y = (1^2^...^100)^(a1^...^a100)
再遍历一遍，可解上面两个方程式
空间O(1), 时间O(N)

vim_dev

回复 5# InMySin

其实本质是异或的逆运算是异或自己吧，
比如c = a^b;    b = c^a; 也就是 a^b^a = b, 一个数异或另一个数两次其值不变。
   

liyapeng90

貌似可以用集合的概念，就是标准模版库里面的

cokeboL

回复 7# folklore


    这个要用 ^ 吧？

crazyhadoop

2L正解

leejqy

方法：
1.【时空复杂度O(nlogn)】排序+扫描，找出重复的那个【挨在一块】，即可求出缺失的；
2.【时空复杂度O(n)】申请数组flag[100]，初始化为0，扫描数组，将相应的flag + 1,如果变成2，说明该值重复，从而可以得到缺失的；
3.【时间复杂度O(n),空间复杂度O(1)】
扫描一次，求得和S1, 和平方和S2：
设缺失的数为X, 重复的为Y；则有方程：
Y - X = S1 - (1+2+3....+100);
Y^2 - X ^2 = S2 - (1^2+2^2+....+100^);
即可求得X，Y
回复 1# rdcwayx


   

sothicor

题目的意思我理解了有点歧义，是100个数字里 拿走一个，还剩99个数，求出缺的那个数，还是说100个数里，有1个唯一重复的数字。
前者的话，用异或能解决，后一个再想想。。

1. #include<stdio.h>
   
2. 
   
3. int get_miss_no(int *data, int n);
   
4. 
   
5. int main(void)
   
6. {
   
7.     int arr[4] = {5,2,1,3}; //假设5个数字中随机扣掉1个，还剩4个
   
8.     printf("\nmiss no is %d\n", get_miss_no(arr,4));   
   
9.     return 0;
   
10. }
    
11. 
    
12. int get_miss_no(int *arr, int n)
    
13. {
    
14.     int miss_no = arr[0];
    
15.     for(int i = 1; i < n; i++)
    
16.                 miss_no ^= arr[i];
    
17.     for(int i = 0; i < n+1; i++)
    
18.         miss_no ^= i+1;
    
19.     return miss_no;
    
20. }
    

复制代码

shang2010

循环一次，但做两个逻辑
1重复检测，2累加

当然循环两次也是OK的

cttnbcj

BITMAP啊 ~~