Code666 (代码贴、代码片段)

[Java] Java在数组中快速查找“和”为指定值的两个元素 →→→→→进入此内容的聊天室

来自 , 2020-11-26, 写在 Java, 查看 110 次.
URL http://www.code666.cn/view/6734fa70
  1. // 快速寻找满足条件的两个数
  2. // 数组中两个数的和满足指定结果
  3. public class Test
  4. {
  5.     static int[] arr =
  6.     {
  7.             1, 5, 9, 3, 4, 7, 6, 2, 8
  8.     };
  9.     static int maxIndex = arr.length - 1;// 索引最大值
  10.     static int sum = 11;// 求两个数的和等于的值
  11.  
  12.     public static void main(String[] args)
  13.     {
  14.         find1(arr);
  15.     }
  16.  
  17.     // 1.所有数字两两组合，计算；时间复杂度O(n*n)
  18.     // 2.先把数组排序，然后利用二分查找在数组中查找,判断sum-arr[i]是否在数组中；时间复杂度O(n*longn)
  19.     // 3.先对数组排序i=0,j=n-1，如果:sum<arr[i]+arr[j] i++;如果:sum<arr[i]+arr[j] j--
  20.     // 如果有序，直接两个指针两端扫描，时间O（N）；如果无序，先排序后两端扫描，时间O（N*logN+N）=O（N*logN），空间始终都为O（1）
  21.     static void find1(int[] arr)
  22.     {
  23.         Arrays.sort(arr);// 对数组排序
  24.         for (int i = 0, j = maxIndex; i < j;)
  25.         {
  26.             if (arr[i] + arr[j] == sum)
  27.             {
  28.                 System.out.println(sum + " = " + arr[i] + " + " + arr[j]);
  29.                 i++;// 没有这一句死循环
  30.             }
  31.             else if (arr[i] + arr[j] < sum)
  32.             {
  33.                 i++;
  34.             }
  35.             else
  36.             {
  37.                 j--;
  38.             }
  39.         }
  40.     }
  41. }
  42. //java/6695

回复 "Java在数组中快速查找“和”为指定值的两个元素"

这儿你可以回复上面这条便签

captcha

贴代码片段 - Code666