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

zhujiang73

回复 4# lxyscls_cu


    通俗易懂，简单直接，好。 {:3_189:}

conn2011

回复 4# lxyscls_cu


    建个索引数组——1-100，初始为{0}
    声明变量 int sum = 0

    录入：
     if 索引数组对应位置的值为0 : 索引数组对应位置的值=1 且 sum +=  索引数组对应位置 (将所有非重复值累加)
   
   得出缺失数: 5050-sum
            

   

cttnbcj

BITMAP啊 ~~

shang2010

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

当然循环两次也是OK的

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. }
    

复制代码

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


   

crazyhadoop

2L正解

cokeboL

回复 7# folklore


    这个要用 ^ 吧？

liyapeng90

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

vim_dev

回复 5# InMySin

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