文字列から繰り返し文字を削除する
1.概要
このチュートリアルでは、文字列から繰り返し文字を削除するためのJavaの手法について説明します。
それぞれの手法について、時間と空間の複雑さについても簡単に説明します。
2.
distinct
を使う
Java 8で導入された
distinct
メソッドを使用して、文字列から重複した文字列を削除することから始めましょう。
以下のコードでは、与えられた文字列オブジェクトから
IntStream
のインスタンスを取得しています。次に、重複を削除するために
distinct
メソッドを使用しています。次に、
forEach
を使用して異なる文字をループし、それらを
StringBuilder
に追加します。
StringBuilder sb = new StringBuilder();
str.chars().distinct().forEach(c -> sb.append((char) c));-
時間の複雑さ:
**
_ O（n）
_
– ループの実行時間は入力文字列のサイズに正比例します -
補助スペース:**
O（n）
–
__distinct
は、順序を維持するために中間の
LinkedHashSet__を作成します。 -
順序を維持します:** はい
そして、Java 8がこのタスクを非常にうまく解決してくれることは素晴らしいことですが、それを私たち自身のロールアップの努力と比較してみましょう。
3.
indexOf
を使う
文字列から重複を削除する単純な方法は、単に入力をループ処理し、メソッド
__indexOf
__を使用して、結果の文字列にその文字がすでに存在するかどうかを調べるだけです。
StringBuilder sb = new StringBuilder();
int idx;
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
idx = str.indexOf(c, i + 1);
if (idx == -1) {
sb.append(c);
}
}-
時間の複雑さ:
_ O（n
n）_ – ループの実行時間は入力データセットのサイズの2乗に正比例 -
補助スペース:**
O（1）
– ループ内にインデックスと文字の値を格納するには一定のスペースが必要です -
順序を維持します:** はい
これには補助スペースがないという利点がありますが、Core Javaのアプローチよりもはるかに遅くなります。
4.文字配列を使う
-
それを
char
配列に変換してから各文字をループ処理し、それを後続のすべての文字と比較することで、文字列から重複を削除することもできます。
以下に示すように、forループを2つ作成し、各要素が文字列内で繰り返されているかどうかを確認しています。重複が見つかった場合は
repeatedCtr
をインクリメントして
StringBuilder
に追加しないようにします。
char[]chars = str.toCharArray();
StringBuilder sb = new StringBuilder();
boolean repeatedChar;
for (int i = 0; i < chars.length; i++) {
repeatedChar = false;
for (int j = i + 1; j < chars.length; j++) {
if (chars[i]== chars[j]) {
repeatedChar = true;
break;
}
}
if (!repeatedChar) {
sb.append(chars[i]);
}
}-
時間の複雑さ:
__ O（n
n）
– 内側と外側のループは両方とも
n
__反復が必要 -
補助スペース:**
O（1）
– 入力文字列の繰り返し文字数に依存する
__repeatedCtr
__を格納するために一定のスペースが必要 -
順序を維持します:** いいえ
繰り返しになりますが、2回目の試行はCore Java製品と比べてパフォーマンスが劣りますが、次の試行でどこに到達するかを見てみましょう。
5.ソートを使う
あるいは、入力文字列をグループの重複にソートすることで、繰り返し文字を排除することができます。 ** そのためには、文字列を
__char a
rrayに変換し、
Arrays
静的メソッド
sort.
を使用してソートする必要があります。最後に、ソートされた
char__配列を反復処理します。
繰り返しのたびに、配列の各要素を前の要素と比較します。要素が異なる場合は、現在の文字を__StringBuilderに追加します。
StringBuilder sb = new StringBuilder();
if(!str.isEmpty()) {
char[]chars = str.toCharArray();
Arrays.sort(chars);
sb.append(chars[0]);
for (int i = 1; i < chars.length; i++) {
if (chars[i]!= chars[i - 1]) {
sb.append(chars[i]);
}
}
}-
時間の複雑さ:
**
__ O（n log n）
– 配列の比較ソートは最悪の場合、時間の複雑さは
O（n log n）__になります。 -
補助スペース:**
O（n）
–
sort
は
O（n）
補助スペースを使用するQuicksortを使用し、
__ toCharArrayは
__Stringのコピーを作成 -
順序を維持します:** いいえ
だから、私たちは時空間のトレードオフを見始めています。ここでは、パフォーマンスを向上させるためにスペースを交換しました。もう一度試してみましょう。
6.
Set
を使う
文字列から繰り返し文字を削除するもう1つの方法は、
Set
を使用することです。出力文字列の文字の順序を気にしないのであれば、
HashSet
を使用できます。それ以外の場合は、挿入順序を維持するために
__LinkedHashSet
__を使用できます。
どちらの場合も、入力文字列をループ処理して各文字を
Set
に追加します。文字がセットに挿入されたら、それを繰り返して
__StringBuilder
__に追加し、結果の文字列を返します。
StringBuilder sb = new StringBuilder();
Set<Character> linkedHashSet = new LinkedHashSet<>();
for (int i = 0; i < str.length(); i++) {
linkedHashSet.add(str.charAt(i));
}
for (Character c : linkedHashSet) {
sb.append(c);
}-
時間の複雑さ:
**
_ O（n）
_
– ループの実行時間は入力文字列のサイズに正比例します -
補助スペース:**
O（n）
–
Set
に必要なスペースは入力ストリングのサイズによって異なります -
順序を維持します。**
_LinkedHashSet –
はい、
HashSet _
–いいえ
そして今、私たちはコアJavaアプローチにマッチしました！これを見つけることは、それが既に明らかにされていることと非常によく似ていることを知ることはそれほどショックではありません。
7.まとめ
-
この記事では、Javaで文字列から繰り返し文字を削除するいくつかの方法について説明しました** これらのメソッドの時間と空間の複雑さも調べました。
いつものように、コードスニペットはhttps://github.com/eugenp/tutorials/tree/master/java-strings[over on GitHub]にあります。