# 2叉树排序缺失元素查找

2019/02/12 16:35

## 问题

1. 在一组相同类型的数据中（对象、数组、字符串、整形等任意类型的数据结构）请用时间空间最优的方式查找缺失的一项。例如有一组数据["A","B","C","D","E","F","G"]，现在给到["B","D","A","F"."G"]，需要找到缺失数据"C"？数据的个数不定。
2. 扩展上面的问题，用最优的方式查找缺失的多项。

## 解决

### 2层循环逐个比对查找

1. 少量数据可行，但是海量数据肯定会非常慢，因为时间复杂度是O(n^2)。而且第一层循环是全遍历，第二层循要遍历n/2。
2. 在比对过程中如果是字符串比对，效率会非常差。

### 编码2叉树查找

{1:"A",2:"B",3:"C",4:"D",5:"E",6:"F",7:"G"}


{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


import copy
import random as rand
import datetime
import time

# 2叉树结构
def __init__(self, value):
self.value = value
self.left = None
self.right = None

def insert(self, value):
if value < self.value:
else:

if self.left is not None:
self.left.insert(value)
else:

if self.right is not None:
self.right.insert(value)
else:

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):
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))


0 评论
0 收藏
0