求兩個字符串的交集
昨天去閱文集團面試月培，遇到這么一道面試題：
寫一個方法
intersection恩急，求兩個字符串的交集。
比如name和age兩個字符串的交集為a,e纪蜒。
這是個很簡單的查找算法，思路如下：
- 將字符串轉換成字符數(shù)組(
array1霍掺、array2)匾荆；- 依次查找
array1中的元素在array2中是否存在；- 如果存在杆烁，說明為共同元素(交集)牙丽，否則為非交集元素；
代碼實現(xiàn)如下：
/**
* 輸出兩個字符串的交集(共同元素)
*/
public static void intersection(String text1, String text2) {
char[] charArray1 = text1.toCharArray(); // 字符串1對應的數(shù)組
char[] charArray2 = text2.toCharArray(); // 字符串2對應的數(shù)據(jù)
for (int i = 0; i < charArray1.length; i++) {
char charI = charArray1[i];
for (int j = 0; j < charArray2.length; j++) {
char charJ = charArray2[j];
if (charI == charJ) {
System.out.println(charI);
}
}
}
}
執(zhí)行方法：
intersection("name", "age");
輸出結果：
a
e
符合預期兔魂。
換其它字符串測試烤芦，結果仍然正確。
到此為止析校，問題已得到解決构罗。
求多個字符串的交集
但這個問題還可以再進一步，如果是求n個字符串的共同元素呢智玻？
思路如下：
- 遍歷第一個字符串中的所有字符
char_i遂唧；- 寫一個方法，判斷
char_i是否在指定的字符數(shù)組中吊奢；- 依次判斷
char_i是否在剩下的字符數(shù)組中盖彭，得到多個結果result_1、result_2...result_n页滚；- 將
result_1召边、result_2...result_n依次做&運算，得到最終結果result裹驰；- 如果
result為true隧熙，說明為交集元素，否則為非交集元素幻林。
代碼實現(xiàn)如下：
第1個方法：判斷字符c是否在字符數(shù)組array中
/**
* 判斷字符c是否在字符數(shù)組charArray中
* 如果在贞盯，返回true，否則返回false
*/
public static boolean isCharInArray(char c, char[] array) {
for (int i = 0; i < array.length; i++) {
char char_i = array[i];
if (c == char_i) {
return true;
}
}
return false;
}
第2個方法：判斷字符c是否同時存在于多個字符數(shù)組arrays中
/**
* 判斷字符c是否同時存在于多個字符數(shù)組中
* 如果同時存在于多個數(shù)組中沪饺，返回true邻悬，否則返回false
*/
public static boolean isCharInArrays(char c, char[]... arrays) {
boolean result = true;
for (int i = 0; i < arrays.length; i++) {
char[] array = arrays[i];
boolean isCharInArray = isCharInArray(c, array);
result = result & isCharInArray;
}
return result;
}
上面的方法也可以寫做以下形式：
/**
* 判斷字符c是否同時存在于多個字符數(shù)組中
* 如果同時存在于多個數(shù)組中，返回true随闽，否則返回false
*/
public static boolean isCharInArrays(char c, char[]... arrays) {
boolean isCharInArrays = true;
for (int i = 0; i < arrays.length; i++) {
char[] array = arrays[i];
boolean isCharInArray = false;
for (int j = 0; j < array.length; j++) {
if (c == array[j]) {
isCharInArray = true;
break;
}
}
isCharInArrays = isCharInArrays & isCharInArray;
}
return isCharInArrays;
}
第3個方法：輸出所有數(shù)組的交集元素
/**
* 輸出所有數(shù)組的交集元素
*/
public static void printCommonChar(char[]... arrays) {
// 遍歷第一個數(shù)組
for (int i = 0; i < arrays[0].length; i++) {
char char_i = arrays[0][i];
// 調用Arrays的靜態(tài)方法剔除第一個數(shù)組
char[][] otherArrays = Arrays.copyOfRange(arrays, 1, arrays.length);
// 判斷char_i是否存在于otherArrays中
boolean result = isCharInArrays(char_i, otherArrays);
if (result == true) {
System.out.println(char_i);
}
}
}
將以上3個方法整合到一起父丰，得到如下結果：
/**
* 輸出多個字符數(shù)組的交集元素
*/
public static void printCommonChar(char[]... arrays) {
// 遍歷第一個數(shù)組的所有元素(字符)
for (int i = 0; i < arrays[0].length; i++) {
char char_i = arrays[0][i];
boolean isCharInArrays = true;
// 除去第一個數(shù)組，從j=1開始遍歷
for (int j = 1; j < arrays.length; j++) {
char[] array = arrays[j];
boolean isCharInArray = false;
for (int k = 0; k < array.length; k++) {
if (char_i == array[k]) {
isCharInArray = true;
break;
}
}
isCharInArrays = isCharInArrays & isCharInArray;
}
if (isCharInArrays) {
System.out.println(char_i);
}
}
}
使用泛型對方法進行改造
至此，求多個字符數(shù)組的交集元素的功能已實現(xiàn)蛾扇，使用泛型對以上方法進行改造攘烛，即可得到一個通用的求數(shù)組交集的方法，如下：
- 使用泛型
T代碼基本類型char- 將元素比較方法由
==替換為equals- 本方法的僅限于求包裝類型數(shù)組的交集
/**
* 輸出多個包裝類型數(shù)組的共有元素
*/
public static <T> void printCommonElements(T[]... arrays) {
// 遍歷第一個數(shù)組的所有元素(字符)
for (int i = 0; i < arrays[0].length; i++) {
T object_i = arrays[0][i];
boolean isCharInArrays = true;
// 除去第一個數(shù)組镀首，從j=1開始遍歷
for (int j = 1; j < arrays.length; j++) {
T[] array = arrays[j];
boolean isCharInArray = false;
for (int k = 0; k < array.length; k++) {
if (object_i.equals(array[k])) {
isCharInArray = true;
break;
}
}
isCharInArrays = isCharInArrays & isCharInArray;
}
if (isCharInArrays) {
System.out.println(object_i);
}
}
}
