快速寻找满足条件的两个数

问题描述

　　能否快速找出一个数组中的两个数字，让这两个数字之和等于一个给定的数字，为了简化起见，我们假设这个数组中肯定存在这样一组或以上符合要求的解。

分析与解法

【解法一】

代码如下：

1 package chapter2shuzizhimei.findtwonumber; 2 /** 3  * 快速寻找满足条件的两个数 4  * 【解法一】 5  * @author DELL 6  * 7  */ 8 public class FindTowNumber1 { 9     //定义一个二元组类10     public static class Tuple{11         public double a;12         public double b;13         public Tuple(double a, double b){14             this.a = a;15             this.b = b;16         }17     }18     //寻找满足条件的两个数19     public static Tuple find(double a[],double sum){20         int n = a.length;21         for(int i=0;i

程序运行结果如下：

数组中和为：10.0的两个数为：9.0 1.0

【解法二】

完整代码如下：

 

1 package chapter2shuzizhimei.findtwonumber; 2 /** 3  * 快速寻找满足条件的两个数 4  * 【解法二】 5  * @author DELL 6  * 7  */ 8 public class FindTowNumber2 { 9     //定义一个二元组类10     public static class Tuple{11         public double a;12         public double b;13         public Tuple(double a, double b){14             this.a = a;15             this.b = b;16         }17     }18     19     //快速排序的一次划分20     public static int partition(double a[], int first, int last) {21         double temp = a[first];22         int i = first, j = last;23         while (i < j) {24             while (i < j && a[j] >= temp) {25                 j--;26             }27             if (i < j)28                 a[i] = a[j];29             while (i < j && a[i] <= temp) {30                 i++;31             }32             if (i < j)33                 a[j] = a[i];34         }35         a[i] = temp;36         return i;37     }38 39     // 快速排序40     public static void quickSort(double a[], int first, int last) {41         if (first >= last)42             return;43         int i = partition(a, first, last);44         quickSort(a, first, i - 1);45         quickSort(a, i + 1, last);46     }47     48     //寻找满足条件的两个数49     public static Tuple find(double a[],double sum){50         int n = a.length;51         quickSort(a,0,n-1);  //从小到大排序52         int i,j;53         for(i=0,j=n-1;i
     
      sum){58                 j--;59             }else{60                 i++;61             }62         }63         return null;64     }65     public static void main(String[] args) {66         double a[] = {3,8,4,9,12,5,1};67         double sum = 9;68         Tuple t = find(a,sum);69         System.out.println("数组中和为："+sum+"的两个数为："+t.a+" "+t.b);70 71     }72 73 }
     

程序运行结果如下：

数组中和为：9.0的两个数为：1.0 8.0