本系列博客习题来自《算法(第四版)》，算是本人的读书笔记，如果有人在读这本书的，欢迎大家多多交流。为了方便讨论，本人新建了一个微信群(算法交流)，想要加入的，请添加我的微信号：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);
}
代码索引
广告
我的首款个人开发的APP壁纸宝贝上线了，欢迎大家下载。
