算法练习(65): 打印两个数组的公共元素(1.4.12)

本系列博客习题来自《算法(第四版)》，算是本人的读书笔记，如果有人在读这本书的，欢迎大家多多交流。为了方便讨论，本人新建了一个微信群(算法交流)，想要加入的，请添加我的微信号：zhujinhui207407 谢谢。另外，本人的个人博客 http://www.kyson.cn 也在不停的更新中，欢迎一起讨论

算法(第4版)

知识点

• 打印两个数组的公共元素

题目

1.4.12 编写一个程序，有序打印给定的两个有序数组（含有 N 个 int 值） 中的所有公共元素，程序在最坏情况下所需的运行时间应该和 N 成正比。

---

1.4.12 Write a program that, given two sorted arrays of N int values, prints all elements that appear in both arrays, in sorted order. The running time of your program should be proportional to N in the worst case.

分析

需要注意的是，这里有两个“有序”：有序打印给定的两个有序数组,
"运行时间应该和 N 成正比"表明增长的数量级为线性的。

答案

// x和y是已经被排序过的数组
public static void sameElements(int[] x, int[] y) {
      for (int i = 0, j = 0; i < x.length && j < y.length;) {
            if (x[i] < y[j]) {
                  i++;
            }else if (x[i] > y[j]) {
                  j++;
            }else {
                  System.out.println(""+ x[i]);
                  i++;
                  j++;
            }
      }
}

测试用例

public static void main(String[] args) {
      int[] b1 = { 1, 2, 3, 5, 4, 5, 6, 77, 7, 8, 8, 9, 1, 11, 22, 234, 90,
                  234, 345 };
      int[] b2 = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
                  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };
      Arrays.sort(b1);
      Arrays.sort(b2);
      sameElements(b1, b2);
}

代码索引

SameElement.java

广告

我的首款个人开发的APP壁纸宝贝上线了，欢迎大家下载。