好贷网好贷款

判断数组中是否存在和等于给定值的两个数

发布时间:2016-12-3 2:14:10 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"判断数组中是否存在和等于给定值的两个数",主要涉及到判断数组中是否存在和等于给定值的两个数方面的内容,对于判断数组中是否存在和等于给定值的两个数感兴趣的同学可以参考一下。

给定一个正序排列的数组arr=[1,4,5,7,11,13]和一个整数num=9,判断arr中的是否存在和为num的两个数 1、时间复杂度为O(n): def ch_equal(arr, num): start_point = 0;end_point = len(arr) - 1 len_arr = len(arr) com_times = len_arr*(len_arr-1)/2 + len_arr #max compare times move_times = 0 while move_times<=com_times and start_point<=end_point: print start_point,end_point if arr[start_point] + arr[end_point] == num: m,n = arr[start_point],arr[end_point] print m,n return m,n if arr[start_point] + arr[end_point] < num: start_point += 1 move_times += 1 if arr[start_point] + arr[end_point] > num: end_point -= 1 move_times += 1 arr = [1,4,5,7,11,13];num = 9 print ch_equal(arr, num)注意点: (1)遍历次数,无序排列(len_arr*(len_arr-1)/2),但是又可能出现同一位置两个数len_arr,所以com_times=len_arr*(len_arr-1)/2 + len_arr (2)由于在不满足相等条件的情况下,start_point一直执行自增操作,end_point一直执行自减操作。若交集至start_point==end_point时还没有满足值出现,此时应该结束查询。另:start_point不能大于数组右边界(len_arr-1),end_point不能小于左边界(0),所以有start_point<len_arr-1,end_point>=0,这种情况会出现arr[4],arr[3]和arr[3],arr[4]位置交换的重复查询 2、时间复杂度为O(n*n) 找出数组中所有可能出现的两个数的组合,把它们放入到set中,使用filter过滤器,找出所有sum()为num的组合 def com_all(): arr = [1,2,4,5,7,11];num = 9 len_arr = len(arr) full_set = set() for i in range(len_arr): for j in range(len_arr-i): print i,len_arr-j-1 full_set.add((arr[i],arr[len_arr-j-1])) filter_result = filter(lambda x:sum(x)==num,full_set) print filter_result

上一篇:C++ Primer总结与内容拓展(第一章)
下一篇:八核版9500odin3线刷通刷以及root教程

相关文章

相关评论