您好,欢迎来到步遥情感网。
搜索
您的当前位置:首页快速找出一个数组中的两个数字,其和等于给定值。

快速找出一个数组中的两个数字,其和等于给定值。

来源:步遥情感网

快速找出一个数组中的两个数字,其和等于给定值。

解法1:穷举法,时间复杂度O(N);

解法2:变通思路,对数组中的每个数字arr[i]都判别sum-arr[i]在不在数组中。这样就变通为一个查找算法。将数组排序,需要时间O(N*logN)。对于每个arr[i]用二分法查找sum-arr[i]的时间复杂度都为O(logN),总计N*O(logN)+ O(N*logN)= O(N*logN)

当然也可以用hash的方法简化查找,但是空间效率加大了。

解法3:首先对数组进行排序,时间复杂度为O(N*logN)

然后令i=0j=n-1,看arr[i]+arr[j]是否等于sum,如果是则结束,如果小于sum,则i=i+1;如果大于sum,则j=j-1。这样只需要在排好序的数组上遍历一次,就可以得到最后的结果,该步操作的时间复杂度为O(N)。两步加起来的时间复杂度为O(N*logN)

查找伪码:

for( i=0,j=n-1; i<j; )

if(arr[i] + arr[j] == sum)

return (i , j);

else if( arr[i] + arr[j] < sum)

i++;

else

j--;

return (-1,-1);

因篇幅问题不能全部显示,请点此查看更多更全内容

Copyright © 2019- obuygou.com 版权所有 赣ICP备2024042798号-5

违法及侵权请联系:TEL:199 18 7713 E-MAIL:2724546146@qq.com

本站由北京市万商天勤律师事务所王兴未律师提供法律服务