问题
- 在一组相同类型的数据中（对象、数组、字符串、整形等任意类型的数据结构）请用时间空间最优的方式查找缺失的一项。例如有一组数据["A","B","C","D","E","F","G"]，现在给到["B","D","A","F"."G"]，需要找到缺失数据"C"？数据的个数不定。
- 扩展上面的问题，用最优的方式查找缺失的多项。
解决
2层循环逐个比对查找
最简单的办法当然是逐项比对，几乎所有语言都提供对象实例、字符串、数字的比对方法。
但是这样做有2个问题：
- 少量数据可行，但是海量数据肯定会非常慢，因为时间复杂度是
。而且第一层循环是全遍历，第二层循要遍历
- 在比对过程中如果是字符串比对，效率会非常差。
编码2叉树查找
可以对所有的事物进行有序编码，然后通过编码索引到对应的元素。编码也没有什么特别的要求，只要每增加一项将编码加一即可。例如上面的例子["A","B","C","D","E","F","G"]，对其编码建立索引：
{1:"A",2:"B",3:"C",4:"D",5:"E",6:"F",7:"G"}
这是一个标准的dict结构（Java中的map结构）。任何时候增加新的项目只要编码加一即可：
{1:"A",2:"B",3:"C",4:"D",5:"E",6:"F",7:"G",8:"ADD ITEM"}
使用编码还有一个好处是还可以查找一组不同类型的数据。
建立编码之后实际上就转换为一个数字查询问题。
如果仅仅是查找一个缺失项，实际上有一个非常简便的算法——求和计算差值：
# origin_numbers是所有编码的列表，例如[1,2,3,4,5,6,7,8,9,10]。
# random_numbers是缺失了一项的编码无序表，例如[6,2,5,4,7,8,9,10,1]。
for _num in origin_numbers:
total_sum = total_sum + _num
for _num in random_numbers:
without_sum = without_sum + _num
差值正好是缺失的项目索引值。
但是如果是查找多个缺失项，只能用2叉树：
import copy
import random as rand
import datetime
import time
# 2叉树结构
class Link:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(self, value):
if value < self.value:
self.__addLeftLeaf__(value)
else:
self.__addRightLeaf__(value)
def __addLeftLeaf__(self, value):
if self.left is not None:
self.left.insert(value)
else:
self.left = Link(value)
def __addRightLeaf__(self, value):
if self.right is not None:
self.right.insert(value)
else:
self.right = Link(value)
def traversal(self, _list, _without):
if self.left is not None:
self.left.traversal(_list, _without)
length = len(_list)
if 0 < length:
tail = _list[length - 1]
diff = self.value - (tail + 1)
if 0 < diff:
for _d in range(1, diff + 1):
_without.append(self.value - _d)
_list.append(self.value)
if self.right is not None:
self.right.traversal(_list, _without)
# 从队列中移除项目
def remove_number(without_size, numbers):
for count in range(without_size):
del numbers[rand.randrange(len(numbers))]
return numbers
# 使用有序数组生成随机数组
def generation_random(without_size, origin_numbers):
origin_numbers_options = copy.copy(origin_numbers)
length = len(origin_numbers)
random_numbers = []
# 随机
while 0 < length:
rand_number = rand.randrange(length)
random_numbers.append(origin_numbers_options[rand_number])
del origin_numbers_options[rand_number]
length = len(origin_numbers_options)
return remove_number(without_size, random_numbers)
#
def generation_origin_numbers(without_size=1, total=10000):
origin_numbers = list(range(total))
return origin_numbers, generation_random(without_size, origin_numbers)
def tree_2_leaf(numbers):
root = Link(numbers[0])
for pos in range(1, len(numbers)):
root.insert(numbers[pos])
# 使用二叉树
_list = []
_without = []
root.traversal(_list=_list, _without=_without)
return _without
def without_one_number(origin_numbers, random_numbers):
print("=============== without_one_number start ==================")
sum_search_start = time.time()
total_sum = 0
without_sum = 0
print("Sum Search Begin.({})".format(datetime.datetime.now().strftime('%H:%M:%S')))
for _num in origin_numbers:
total_sum = total_sum + _num
for _num in random_numbers:
without_sum = without_sum + _num
tree_search_start = sum_search_end = time.time()
print("Sum Search Complete.({})".format(datetime.datetime.now().strftime('%H:%M:%S')))
print("Timer:{} S".format(sum_search_end - sum_search_start))
print("Total Sum:{}".format(total_sum))
print("Without One Number Sum:{}".format(without_sum))
print("Without Number:{}".format(total_sum - without_sum))
print("---")
print("2 Tree Search Begin.({})".format(datetime.datetime.now().strftime('%H:%M:%S')))
without_number = tree_2_leaf(random_numbers)
print("2 Tree Complete.({})".format(datetime.datetime.now().strftime('%H:%M:%S')))
print("Timer:{} S".format(time.time() - tree_search_start))
print("Without Element:{}".format(without_number))
print("=============== without_one_number end ==================")
def without_multi_number(random_numbers):
print("=============== without_multi_number start ==================")
start = time.time()
print("Search Begin.({})".format(datetime.datetime.now().strftime('%H:%M:%S')))
without_number = tree_2_leaf(random_numbers)
print("Search End.({})".format(datetime.datetime.now().strftime('%H:%M:%S')))
print("Timer:{} S".format(time.time() - start))
print("Without Element:{}".format(without_number))
print("=============== without_multi_number end ==================")
if __name__ == '__main__':
print("Generation Numbers Begin.({})".format(datetime.datetime.now().strftime('%H:%M:%S')))
generation_number_start = time.time()
origin, random = generation_origin_numbers()
print("Generation Numbers Complete.({})".format(datetime.datetime.now().strftime('%H:%M:%S')))
generation_number_end = time.time()
print("Timer:{} S".format(generation_number_end - generation_number_start))
without_one_number(origin, random)
without_multi_number(remove_number(4, random))
