现在有一万（1-10000）的个数，假如拿掉的是两个数，怎么才能找出拿掉的数？

teebye

:wink:

thetinker

试着回一贴。

#!/usr/bin/env python #coding=utf-8 import time """全局变量""" numList = [] maxnum = 0 headtag = 0 tailtag = 0 midtag = 0 def SearchNum(missingnum): &nbsp;&nbsp;&nbsp;&nbsp;"""递归折半查找 &nbsp;&nbsp;&nbsp;&nbsp;""" &nbsp;&nbsp;&nbsp;&nbsp;global headtag &nbsp;&nbsp;&nbsp;&nbsp;global tailtag &nbsp;&nbsp;&nbsp;&nbsp;global midtag &nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;#print headtag,midtag,tailtag &nbsp;&nbsp;&nbsp;&nbsp;if tailtag - headtag < 3: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if numList[headtag] != headtag + 1: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;missingnum.append(headtag + 1) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;midtag = headtag &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return 0 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;elif numList[midtag] != midtag + 1: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;missingnum.append(midtag + 1) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return 0 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;missingnum.append(tailtag + 1) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;midtag = tailtag &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return 0 &nbsp;&nbsp;&nbsp;&nbsp;if numList[midtag] == midtag + 1: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;headtag = midtag &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;midtag = int((headtag + tailtag) / 2) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;SearchNum(missingnum) &nbsp;&nbsp;&nbsp;&nbsp;elif numList[midtag] > midtag + 1: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;tailtag = midtag &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;midtag = int((headtag + tailtag) / 2) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;SearchNum(missingnum) &nbsp;&nbsp;&nbsp;&nbsp; def SetNumList(): &nbsp;&nbsp;&nbsp;&nbsp;"""初始化数据 &nbsp;&nbsp;&nbsp;&nbsp;""" &nbsp;&nbsp;&nbsp;&nbsp;global numList &nbsp;&nbsp;&nbsp;&nbsp;global maxnum &nbsp;&nbsp;&nbsp;&nbsp;global headtag &nbsp;&nbsp;&nbsp;&nbsp;global tailtag &nbsp;&nbsp;&nbsp;&nbsp;global midtag    &nbsp;&nbsp;&nbsp;&nbsp;numList = range(1,1000001) &nbsp;&nbsp;&nbsp;&nbsp;maxnum = len(numList) &nbsp;&nbsp;&nbsp;&nbsp;numList.remove(3434) &nbsp;&nbsp;&nbsp;&nbsp;numList.remove(607068) &nbsp;&nbsp;&nbsp;&nbsp;headtag = 0 &nbsp;&nbsp;&nbsp;&nbsp;tailtag = len(numList) - 1 &nbsp;&nbsp;&nbsp;&nbsp;midtag = int(tailtag / 2) def InsertNumList(position,num): &nbsp;&nbsp;&nbsp;&nbsp;"""插入缺失数 &nbsp;&nbsp;&nbsp;&nbsp;""" &nbsp;&nbsp;&nbsp;&nbsp;global numList &nbsp;&nbsp;&nbsp;&nbsp;numList.insert(position,num) &nbsp;&nbsp;&nbsp;&nbsp; def ResetGlobalParam(): &nbsp;&nbsp;&nbsp;&nbsp;"""重置标志位 &nbsp;&nbsp;&nbsp;&nbsp;""" &nbsp;&nbsp;&nbsp;&nbsp;global headtag &nbsp;&nbsp;&nbsp;&nbsp;global tailtag &nbsp;&nbsp;&nbsp;&nbsp;global midtag &nbsp;&nbsp;&nbsp;&nbsp;headtag = 0 &nbsp;&nbsp;&nbsp;&nbsp;tailtag = maxnum - 1 &nbsp;&nbsp;&nbsp;&nbsp;midtag = int(tailtag / 2) if __name__ == "__main__": &nbsp;&nbsp;&nbsp;&nbsp;print "Method 1" &nbsp;&nbsp;&nbsp;&nbsp;SetNumList() &nbsp;&nbsp;&nbsp;&nbsp;beginTime = time.time() &nbsp;&nbsp;&nbsp;&nbsp;missingnum = [] &nbsp;&nbsp;&nbsp;&nbsp;SearchNum(missingnum) &nbsp;&nbsp;&nbsp;&nbsp;#print missingnum &nbsp;&nbsp;&nbsp;&nbsp;#print midtag &nbsp;&nbsp;&nbsp;&nbsp;InsertNumList(midtag,missingnum[0]) &nbsp;&nbsp;&nbsp;&nbsp;ResetGlobalParam() &nbsp;&nbsp;&nbsp;&nbsp;SearchNum(missingnum) &nbsp;&nbsp;&nbsp;&nbsp;print missingnum &nbsp;&nbsp;&nbsp;&nbsp;#print midtag &nbsp;&nbsp;&nbsp;&nbsp;endTime = time.time() &nbsp;&nbsp;&nbsp;&nbsp;print endTime - beginTime

chirking

假设这两个数是A和B
用xor求出 A^B
用加减法求出 A+B
然后呢...
二元一次方程...

keeng2008

2楼的代码是对于排好序的列表。
楼主，这数据是不是排好序的，问题都不详细。

cnsunus

#产生拿掉两个数的数列L0 l0=list(range(1,10001)) x1=int(input("1'st Num:")) x2=int(input("2'st Num:")) l0.remove(x1) l0.remove(x2) #-------------BEGIN--------------- #产生完整的1-10000的数列L1 l1=list(range(1,10001)) #将L0从L1中拿掉 l2=list(set(l1)-set(l0)) #余下的就是你拿走的 print('You have:', l2) #--------------END----------------

[ 本帖最后由 cnsunus 于 2009-7-21 11:33 编辑 ]

cookis

1. 
   
2. cuisw@shaowei:~/codes$ cat find_num.py
   
3. #!/usr/bin/python
   
4. # -*- coding: utf-8 -*-
   
5. 
   
6. num_list = range(0, 1000000)
   
7. 
   
8. num_list.remove(4567)
   
9. num_list.remove(90)
   
10. 
    
11. cmp_list = [0 for i in range(0, 1000000)]
    
12. for i in num_list:
    
13.   cmp_list[i] = 1
    
14. 
    
15. print [i for i in range(0, 1000000) if cmp_list[i] == 0]
    
16. cuisw@shaowei:~/codes$ time python find_num.py
    
17. [90, 4567]
    
18. 
    
19. real        0m0.823s
    
20. user        0m0.696s
    
21. sys        0m0.080s
    
22. cuisw@shaowei:~/codes$
    
23. 
    

复制代码