排序数组中找和的因子

Java基础

浏览数:132

2019-10-8

题目:给定已排序数组,不重复打印arr中所有相加和为k的不降序二元组?扩展题:三元组呢?如输入arr =  {-8,-4,-3,0,2,4,5,8,9,10},k=10,那么该输出(0,10)  (2,8) 。

思路:一看这道题目就很容易想到循环暴力破解,时间复杂度为n²。这样肯定不太理想,所以得换解法,题目已经说了是已排序数组,那么就可以用二分查找,先给定首指针元素,然后再用K去减去首指针元素,再去二分查找剩下一个元素在不在数组。然后首指针右移,这样就能全部找出来了,这种解法的时间复杂度为NlgN。这道题还有另一种解法,我们可以设置左右指针同时扫描,扫描出两个数之和等于K,那么这两个数就是要找的那两个数。

代码:

 1 public class 查找和的因子 {
 2     public static void main(String[] args) {
 3         int []arr =  {-8,-4,-3,0,2,4,5,8,9,10};
 4         int k = 10;
 5         f(arr,k);
 6         f2(arr,k);
 7     }
 8     // 解法一
 9     private static void f(int[] arr, int k) {
10         System.out.print("解法一:");
11         for (int i = 0; i < arr.length; i++) {
12             int t = binarySearch(arr, i+1, arr.length-1, k-arr[i]);  // 注意这儿的传参
13             if (t!=-1) {
14                 System.out.print("("+arr[i]+","+arr[t]+")  ");
15             }
16         }
17         System.out.println();
18     }
19     //  解法二:
20     static void f2(int []arr,int k){
21         // p 为左指针, r 为右指针
22         int p = 0;
23         int r = arr.length-1;
24         System.out.print("解法二:");
25         while(p<r){
26             if ((arr[p]+arr[r])<k) {
27                 p++;
28             }else if ((arr[p]+arr[r])==k) {
29                 System.out.print("("+arr[p]+","+arr[r]+")  ");
30                 p++;
31             }else {
32                 r--;
33             }
34         }
35     }
36     // 注意返回的是下标
37     static int binarySearch(int []arr,int low,int high,int key){
38         if (low>high) {
39             return -1;
40         }
41         int mid = low + ((high - low)>>1);
42         int midVal = arr[mid];
43         if (midVal<key) {
44             return binarySearch(arr, mid+1, high, key);
45         }else if (midVal>key) {
46             return binarySearch(arr, low, mid-1, key);
47         }else {
48             return mid;
49         }
50     }
51 }

结果:

  

 注意:在实际应用中,要考虑升序和降序两种情况,就比如上题,我就只考虑了升序一种情况,当我把数组改为降序排列的时候,程序就运行不出来了。

作者:|旧市拾荒|