如何快速查找到数组中的某个数字

时间:2024-10-26 00:48:31

1、快速找出一个数组中的两个数字,让这两个数字之和等于一个给定的值,为了简化起见,我们假设这个数组中肯定存在至少一组符合要求的解。

如何快速查找到数组中的某个数字

2、假如有如下的两个数组,如图所示: 5,6,1,4,7,9,8 给定Sum= 10 1,5,6,7,8,9 给定Sum= 10首先对数组进行排序,时间复杂度为(N*log2N)

如何快速查找到数组中的某个数字

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

如何快速查找到数组中的某个数字

4、两步加起来总的时间复杂度O(N*log2N),下面这个程序就利用了这个思想,代码如下所示:

如何快速查找到数组中的某个数字
如何快速查找到数组中的某个数字

5、bool getSumNum(int[] arr,int Sum), //arr为数组,Sum为和 { int i,j; for(i = 0, j = n-1; i < j ; ) { if(arr[i] + arr[j] == Sum) return true; else if(arr[i] + arr[j] < Sum) i++; else j--; }

如何快速查找到数组中的某个数字

6、刚开始一直无法理解这样一定可以找到这个和吗?难道不会漏掉了解的位置。可以这么理解,假如排好序后的数组为1,3,6,a,9,12,17,28,b,35,46 ,那么i最初指向1的位置,j最初指向46的位置,比如所求的是Sum=a+b,a<b,a和b在数组中的某位置上。

如何快速查找到数组中的某个数字
© 手抄报圈