二つの文字列または複数の文字列の中にはどのような同じ文字のアルゴリズムがありますか?
例えば、現在は2つの文字列String sとString tがあり、この2つの文字列の中に同じ文字が含まれていることを見つけて返します。
/**
*
* @param s
* @param t
* @return
*/
static char []solution(char[] s,char[] t) {
char[] chars = new char[Math.max(s.length,t.length)];
int index = 0;
for (int i = 0;i < s.length;i ++) {
for (int j = 0;j < t.length;j ++) {
if (s[i] == t[j]) {
chars[index ++] = s[i];
}
}
}
char[] result= new char[index];
System.arraycopy(chars,0,result,0,index);
return result;
}
このアルゴリズムの効率は高くなく、複雑さはO(n 2)である。次に効率の高いアルゴリズムを見ます。/**
*
* @param s
* @param t
* @return
*/
static char[]solution2(char[] s,char[] t) {
HashSet set = new HashSet<>();
char[] chars = new char[Math.max(s.length,t.length)];
int index = 0;
for (char c : s)
set.add(c);
int res = 0;
for (char c : t) {
if (!set.add(c)) {
chars[index ++] = c;
}
}
char[] result= new char[index];
System.arraycopy(chars,0,result,0,index);
return result;
}
アルゴリズムの2つの巧は、HashSetデータ構造を使用して、HashMapを使用して、addメソッドの戻り値は、hashSetにこのchar値があるかどうかを表しています。ある場合は重複しています。同じ文字が見つかっていますが、これはまだ効率的ではありません。次に、最適な計算方法を見ます。/**
*
* @param s
* @param t
* @return
*/
static char [] findRepeatCharZ(char[] s,char[] t) {
char [] a = new char['z' - 'A' + 1];
char[] tmp = new char['z' - 'A' + 1];
for (char c : s) {
a[c - 'A'] = 1;
}
int i = 0;
for (char c : t) {
if (a[c - 'A'] == 1) {
tmp[i ++] = (c);
}
}
char[] result= new char[i];
System.arraycopy(tmp,0,result,0,i);
return result;
}
このアルゴリズムは、ascii値間の差分値を活用して、配列aにおける文字のindexを計算してindexの値を1に設定し、文字セットtにおいて、各文字indexを計算して、このindexがaに対応する値が1かどうかを検索し、1であれば、tにおいて現在計算されている文字は、2つの文字セットにある同じ文字です。このアルゴリズムはn文字列の中に倒してもいいです。同じ文字がありますか?/**
*
* @param s
* @param t
* @return
*/
static char [] findRepeatCharZ(char[] ...strings) {
if (strings == null || strings.length == 0) {
return null ;
}
if (strings.length == 1) {
return strings[0];
}
char[] reslut = findRepeatCharZ(strings[0],strings[1]);
for (int i = 2;i < strings.length;i ++) {
reslut = findRepeatCharZ(reslut,strings[i]);
}
return reslut;
}
このアルゴリズムは中国語の漢字を繰り返すアルゴリズムをひっくり返して検索することもできます。中国語の範囲が広いので、メモリの容量を占用するのは比較的大きいかもしれませんが、すべての中国語の個数は数万個しかなく、数十kバイトだけでいいです。ただし、charタイプはすべての中国語に入れられないかもしれません。アルゴリズムはここでは与えられません。