问题
有两个int32位的无序数组找出同时包含的数字。 数组长度分别为M和N。
思路一
暴力搜索
采用循环遍历找出相同的数值。
def find_same(array1, array2):
found = []
for i in array1:
for j in array2:
if i == j:
found.append(i)
break # 找出一个值即可
return found
if __name__ == '__main__':
print(find_same([1, 3, 2, 4, 5], [3, 4, 5]))
空间复杂度 O(1)
时间复杂度 O(M)*O(N)
思路二
排序后搜索
对较短的一个数据进行排序, 然后进行二分查找
def binary_search(value, arr):
low = 0
high =<