Chinaunix首页 | 论坛 | 博客
  • 博客访问: 268450
  • 博文数量: 138
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 971
  • 用 户 组: 普通用户
  • 注册时间: 2015-03-03 10:05
文章分类

全部博文(138)

文章存档

2016年(1)

2015年(137)

我的朋友

分类: C/C++

2015-08-22 15:47:51

【找一个数,排序后二分;找两个数(对其和有要求),排序后从两边往中间凑,当然也要先排序;找四个数之和,两两一对,构造n^2个元素,转换成两个数之和】
 2-sum, 3-sum这两个问题其实都比较简单。他们演化的思路需要稍微费一点转折,不过当明白其中的一个诀窍之后后面的各种变形也都很简单了。最早牵涉到这个问题还是在12年我们组织面试招人的时候,海涛同学出了个这样的问题,求满足等式a^3 + b^3 + c^3 = d^3 的所有a, b, c, d值。其中a, b, c,  d所在区间为[1, 100000]。对于这种问题,似乎最不济的人也可以想到一个办法,就是我纯粹的去遍历每个数值这么蛮算。当时也是一时没有找到很好的办法。

    好了,我们先不急着考虑怎么解决这个问题,先来看看一个更加简单的问题形式。有时候,很多复杂的问题其实就是从一些简单的问题本身衍生出来的。

 

2-sum

    我们先来看这个问题的简单描述,假设有一组数字int[] a,给定一个数字sum,我们希望能够找到数组中是否有两个数字a, b, 他们的和等于数字sum。也就是我们希望找到两个数字使得a + b = sum。

    对于这种问题,我们不能说完全没有思路,只是有一个选择好坏的问题。因为这里只是给定了一组数字,它们是无序排列的。如果要找到所有符合两个数字相加等于目标数字的组合,可以使用最简单的一个双重遍历循环,它的伪代码如下:

 

Java代码  收藏代码
  1. for(int i = 0; i < array.length - 1; i++) {  
  2.     for(int j = i + 1; j < array.length; j++) {  
  3.         if(a[i] + a[j] == sum)  
  4.             // process and record work  
  5.     }    
  6. }  

    通过这种方式我们肯定可以找到所有的数对,只是针对这样一个问题,它们的时间复杂度就达到了O(N * N) 。那么,有没有更好的办法使得它更加有效率一些呢?

    这个时候,如果我们想到一些排序的算法,它们的时间复杂度多半都是在O(NlogN)这个级别的。如果对这些数字排序之后,我们能不能使得查找的效率更高一些呢?假定一个数组排序了,我们如果要查找里面的元素,不就可以直接用二分搜索了吗?而二分搜索的时间复杂度仅仅是O(logN),这样不就可以加快执行速度了么?

    所以,这里的一种改进思路就是首先对数组排个序,这样花的时间为O(NlogN),然后既然要查找里面a + b = sum的值,我们可以遍历整个数组,然后来查找数组里是否有sum - a的元素。这样这个遍历加上查找的时间复杂度也是O(NlogN)。有了这个思路,我们也就可以很容易得到如下的代码了:

 

Java代码  收藏代码
  1. public static int twoSum(int sum, int[] array) {  
  2.         Arrays.sort(array);  
  3.         int length = array.length;  
  4.         int count = 0;  
  5.         for(int i = 0; i < length; i++) {  
  6.             int position = find(sum - array[i], array);  
  7.             if(position > 0) {  
  8.                 System.out.printf("value: %d, position: %d\n",   
  9.                     array[i], position);  
  10.                 count++;  
  11.             }  
  12.         }  
  13.   
  14.         return count;  
  15.     }  

    在代码里为了简化一些步骤,直接使用了java.util.Arrays的sort方法。这里的排序实际上是用到了快速排序的过程。这里find方法就是我们定义的一个二分查找方法,在以前的一些文章里也有谈到过,这里就直接把代码贴过来了:

 

Java代码  收藏代码
  1. public static int find(int v, int[] a) {  
  2.         int l = 0;  
  3.         int r = a.length - 1;  
  4.         int mid;  
  5.         while(l <= r) {  
  6.             mid = l + (r - l) / 2;  
  7.             if(a[mid] > v)  
  8.                 r = mid - 1;  
  9.             else if(a[mid] < v)  
  10.                 l = mid + 1;  
  11.             else  
  12.                 return mid;  
  13.         }  
  14.         return -1;  
  15.     }  

     这样,我们通过将数组排序,得到了一个O(NlogN)时间复杂度的解决方法。现在我们再来更进一步看看3-sum的问题。

 

3-sum

    如果说前面2-sum对应的是a + b = c这样的问题,这里相当于增加了一个维度,我们希望对应一个a + b + c = d。这里增加了这么一个变量,也增加了一点复杂度。原来对应两个元素,我们遍历数组,根据指定遍历的元素来查找sum - b的值。那么这里增加的元素我们也可以做一个类似的思考,我们最终来根据a求sum - b -c的值。 那么从实现的角度来说,我们只是需要多增加一个循环,在这个循环里取和前面不同的值。这种思路是在2-sum的基础上延伸出来的,因为比较简单,我们就列一下它的伪代码实现:

 

Java代码  收藏代码
  1. public static int count(int[] array) {  
  2.     Arrays.sort(array);  
  3.     int length = array.length;  
  4.     int count = 0;  
  5.     for(int i = 0; i < length; i++) {  
  6.         for(int j = i + 1; j < length; j++) {  
  7.             if(find(sum - a[i] - a[j], array) > 0)   
  8.                 count++;  
  9.         }  
  10.     }  
  11.     return count;  
  12. }  

     如果用这种办法的话,我们的时间复杂度为O(N*NlogN)。虽然看起来还是可以接受,但是有没有更好的办法呢?

    假定我们有一个如下的排序的数组:

    

        如果我们要求两个数,使得它们的和为某个特定的值,那么我们的目的就是要找到所有符合这个条件的数值对。假定在这里我们要求使得任意两个数字的和为9, 那么对于这个给定的数字来说。其实从数学的角度我们可以这样来看。如果我们取这个目标数字9的一半,也就是4.5,用它来划分这个数组的话,它左边的数字表示比它小的,它右边的数字表示比它大的。那么这里对应的一个划分则如下图所示:

    实际上,如果我们需要去求得和为9的两个数字,肯定他们中间有一个在前面这个部分,一个在后面这个部分。而且还有一个更加有意思的特点,比如说这里的2 + 7 = 9。那么我们将左边的数字往右一个,右边的往左一个,他们还是有可能凑成一对符合条件的数字。这样我们就找到另外一种有意思的规律。

    我们一开始从数组的开头和结尾去这两个数字,如果存在两个数字它们的和等于目标数字。它们肯定是一个大于我们给定数字的一半而另一个小于它的一半。我们可以先计算这两个数字的和,用它们来比较目标数字。如果大于目标数字,则右边的下标往左移一步,相当于将它们的和调小一点,如果小于的话,则移动左边的下标往右一步。这样我们就可以通过这样一次循环找到所有符合条件的数字了。

     按照这种思路,我们可以得到如下的代码:

 

Java代码  收藏代码
  1. public static void threeSums(int sum, int[] a) {  
  2.         Arrays.sort(a);  
  3.         for(int i = 0; i < a.length; i++) {  
  4.             System.out.println(findAllMatches(sum - a[i], a));  
  5.         }  
  6.     }  
  7.   
  8.     public static int findAllMatches(int v, int[] a) {  
  9.         int l = 0;  
  10.         int r = a.length - 1;  
  11.         int count = 0;  
  12.         while(l < r) {  
  13.             if(a[l] + a[r] < v)  
  14.                 l++;  
  15.             else if(a[l] + a[r] > v)  
  16.                 r--;  
  17.             else {  
  18.                 System.out.printf("l: %d, r: %d\n", l, r);  
  19.                 count++;  
  20.                 l++;  
  21.                 r--;  
  22.             }  
  23.         }  
  24.   
  25.         return count;  
  26.     }  

     按照前面的分析,我们对数组排序用的时间为O(NlogN),我们匹配两个数字的和,用的时间为O(N),但是这一步外面还嵌套一个遍历数组的循环,所以它的时间复杂度为O(N*N)。这样, 整个问题的时间复杂度为O(N^2)。

    我们这样就解决了3-sum的一般问题。实际上还有很多这种问题的变化。比如最开始我提到的那个问题,还有一种就是我要求的这个sum不是固定的,它也是在这个数组里。这个时候,我们解决问题的办法还是差不多,只是对于这个变化的sum要做一个遍历。

 

4-sum

  现在,我们再把问题复杂化一步,假设来求一个4-sum的问题。就是给定一个数组,要求里面是否存在a + b + c + d = sum的情况。在前面两种情况下,我们都是将问题归结为a + b = sum, a + b = sum - c等这样的情况。提高问题解决效率的关键点在于将数组排序。在更加多了一个参数的情况下,是否可以利用原来的思路呢?

  在2-sum的情况下,我们只要给定一个a,然后取查找数组里是否存在等于sum - a的情况,也可以采用线性查找的方法,从数组的两头并进,找到符合条件的数对。3-sum的情况也类似,只是要循环遍历整个数组。这里所有遍历的元素就是构成可能满足条件的数组元素。对于4-sum的情况,我们可以将条件转化为a + b = sum - c - d。粗看来,这样没有多少帮助。这里相当于要找到两个数的和,它们等于sum减去另外两个数。嗯,原来的等式其实也相当于a + b = sum - (c + d)。这样概括起来的话,不就是相当于求两个数的和,它们等于sum减去另外两个数的和吗?

  到了这一步,就到了问题的关键了。两个数的和,对于一个给定的数组来说,它们构成了一个集合,假设数组元素个数为n,那么任意两个数的和构成一个C(n, 2)的组合,它们也构成了一个集合。相当于有(n * n + 1) / 2个元素。也可以笼统的称之为n^2个元素。而如果我们将前面数组中两个元素的和当做一个元素的话,这不就相当于求a = sum - b吗?只是这里a, b都是由原来数组里两个元素的和构成。这样,原来的问题就可以归结为从n^2的元素里求两个数的和为sum的问题,也就是一个2-sum的问题了。

  更细化一步,解决这个问题需要如下几个步骤:

1. 构造任意两个元素相加得到的集合。

2. 对这个集合排序。

3. 查找集合里所有符合a + b = sum的元素对。

  从第一步得到的两个元素和的集合有n^2个,时间复杂度为O(N^2)。而第二步进行排序的时间复杂度为O(N^2logN^2),也就是O(N^2logN)。

  结合前面的讨论,对这个问题的详细代码实现就比较简单了。这里仅对第1,2步的描述做一个实现。详细代码如下:

Java代码  收藏代码
  1. public int[] generateSums(int[] a) {  
  2.     int n = a.length;  
  3.     int size = n * (n + 1) / 2;  
  4.     int k = 0;  
  5.     int[] result = new int[size];  
  6.     for(int i = 0; i < n; i++) {  
  7.         for(int j = i + 1; j < n; j++)  {  
  8.             result[k] = a[i] + a[j];  
  9.             k++;  
  10.         }  
  11.     }  
  12.   
  13.     return Arrays.sort(result);  
  14. }  

    这部分代码比较简单,就是一个生成所有相加元素的组合, 这个问题的核心其实已经演化为一个元素集合查找的问题了。当然,在需要输出对应的元素i, j的时候,我们可能需要将它们和对应的和元素关联起来。这里可以通过将定义的数组result修改为一个自定义的类型,里面包含进行比较的元素以及关联的两个索引元素就可以。这部分就不再赘述。

 

 

总结

    2-sum, 3-sum的问题在一定的问题规模下,是可以找到有效的方法来解决的。我们常用的办法就是首先针对这个数组排序,然后再去通过二分法查找目标值。还有一种就是通过从排序后的数组两头来凑这个给定的目标值。基本上所有这些问题的变体都可以通过这几种方法来解决。而且这些解决方法的时间复杂度还是相当客观的,对于2-sum来说它达到了O(NlogN),对于3-sum来说,它可以达到O(N^2)。以前也有人总结过,说碰到这种和数组的东西打交道时,如果实在没什么思路,干脆就不管三七二十一给它排个序,也许思路就有了,看来还是有点道理的。

 这是最近的一次补充,在参考一些文章之后,发现针对多个元素求和的问题其实还有一些新的思路,主要是将一些元素的和当做一个集合,这样任何两个或者若干个元素的和它们都可以当做一个对等的集合。这样我们的问题就归结为在一个广义的集合里求更少元素的和问题。精妙之处就在于此。有了这个基础,我们在这个基础上做更多元素的类推,也找到了一个更加有力的方法。

阅读(1123) | 评论(0) | 转发(0) |
0

上一篇:正则表达式

下一篇:intentService

给主人留下些什么吧!~~