Code666 (代码贴、代码片段)

[Java]  求两个已排序的数组的交集 →→→→→进入此内容的聊天室

来自 , 2020-07-01, 写在 Java, 查看 103 次.
URL http://www.code666.cn/view/41bfd20a
  1. 下面这个方法 要求两个数组是已排序的
  2.  
  3. Java codepackage com.haojia.algorithm;
  4.  
  5. /**
  6.  * 求两个已排序的数组的交集
  7.  * 
  8.  * @author July
  9.  * 
  10.  */
  11. public class Intersect {
  12.     public static void go(int[] a, int[] b) {
  13.         int i = 0;
  14.         int j = 0;
  15.  
  16.         while (i < a.length && j < b.length) {
  17.             if (a[i] < b[j]) {
  18.                 i++;
  19.             } else if (a[i] > b[j]) {
  20.                 j++;
  21.             } else {
  22.                 System.out.print(a[i] + " ");
  23.                 i++;
  24.                 j++;
  25.             }
  26.         }
  27.     }
  28.  
  29.     public static void main(String[] args) {
  30.         int[] a = { 1, 5, 8, 10, 14, 15, 17, 18, 20, 22, 24, 25, 28 };
  31.         int[] b = { 2, 4, 6, 8, 10, 12 };
  32.         go(a, b);
  33.     }
  34.  
  35. }
  36. ------解决方案--------------------
  37. Java codeimport java.util.Arrays;
  38. import java.util.HashSet;
  39. import java.util.Random;
  40. import java.util.Set;
  41. public class SelectBag {
  42.     public static int find(int key,int[] N){
  43.         int lb=0;
  44.         int ub=N.length-1;
  45.         int in;
  46.         while(true){
  47.             in=(lb+ub)/2;
  48.             if(N[in]==key)
  49.                 return in;
  50.             else if(lb>ub)
  51.                 return -1;
  52.             else{
  53.                 if(N[in]<key)
  54.                     lb=in+1;
  55.                 else
  56.                     ub=in-1;
  57.             }
  58.         }
  59.     }
  60.     public static void main(String[] args){
  61.         int[] M=RandomIntArray(30);
  62.         int[] N=RandomIntArray(30);
  63.         System.out.println(Arrays.toString(M));
  64.         System.out.println(Arrays.toString(N));
  65.         Set<Integer> list=new HashSet<Integer>();
  66.         for(int m:M){
  67.             int getInt=find(m,N);
  68.             if(getInt!=-1)
  69.                 list.add(N[getInt]);
  70.         }
  71.         System.out.println("两个数组中重复的元素有："+list);
  72.     }
  73.     
  74.     public static int[] RandomIntArray(int count){
  75.         int[] array=new int[count];
  76.         Random r=new Random();
  77.         for(int i=0;i<count;i++){
  78.             array[i]=r.nextInt(100);
  79.         }
  80.         Arrays.sort(array);
  81.         return array;
  82.     }
  83.     
  84. }
  85. 结果：
  86. [1, 3, 8, 11, 12, 20, 22, 22, 31, 34, 37, 40, 41, 45, 48, 49, 50, 51, 57, 69, 72, 73, 84, 84, 85, 93, 93, 93, 98, 98]
  87. [0, 4, 4, 9, 12, 16, 26, 26, 28, 32, 36, 41, 42, 44, 48, 48, 55, 56, 61, 65, 72, 72, 73, 75, 76, 78, 83, 84, 89, 94]
  88. 两个数组中重复的元素有：[84, 48, 41, 72, 12, 73]//源代码片段来自云代码http://yuncode.net
  89.                        

回复 " 求两个已排序的数组的交集"

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

captcha

贴代码片段 - Code666