本系列博客習(xí)題來(lái)自《算法(第四版)》烦周，算是本人的讀書筆記，如果有人在讀這本書的怎顾，歡迎大家多多交流读慎。為了方便討論，本人新建了一個(gè)微信群(算法交流)槐雾，想要加入的夭委，請(qǐng)?zhí)砑游业奈⑿盘?hào)：zhujinhui207407 謝謝。另外募强，本人的個(gè)人博客 http://www.kyson.cn 也在不停的更新中株灸，歡迎一起討論
算法(第4版)
知識(shí)點(diǎn)
- 打印兩個(gè)數(shù)組的公共元素
題目
1.4.12 編寫一個(gè)程序，有序打印給定的兩個(gè)有序數(shù)組（含有 N 個(gè) int 值） 中的所有公共元素擎值，程序在最壞情況下所需的運(yùn)行時(shí)間應(yīng)該和 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.
分析
需要注意的是，這里有兩個(gè)“有序”：有序打印給定的兩個(gè)有序數(shù)組,
"運(yùn)行時(shí)間應(yīng)該和 N 成正比"表明增長(zhǎng)的數(shù)量級(jí)為線性的鸠儿。
答案
// x和y是已經(jīng)被排序過的數(shù)組
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++;
}
}
}
測(cè)試用例
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);
}
代碼索引
廣告
我的首款個(gè)人開發(fā)的APP壁紙寶貝上線了屹蚊，歡迎大家下載。
