HashSetとListのパフォーマンスの違い

結論:HashSetの方が高パフォーマンス

使用問題文-LeetCode 345

文字列 s を指定すると、文字列内のすべての母音のみを反転して返します。

母音は「a」、「e」、「i」、「o」、「u」で、小文字と大文字の両方で複数回出現することがあります。

コード HashSetを使用　実行時間:5ms メモリー:44.46MB

class Solution {
    public String reverseVowels(String s) {
        char [] c = s.toCharArray();
        HashSet<Character>list = new HashSet<>();
        list.add('a');
        list.add('i');
        list.add('u');
        list.add('e');
        list.add('o');
        list.add('A');
        list.add('I');
        list.add('U');
        list.add('E');
        list.add('O');

        int Rindex=0, Lindex=c.length-1;
        while(Rindex < Lindex){
            if(!list.contains(c[Rindex])){
                Rindex++;
            }

            if(!list.contains(c[Lindex])){
                Lindex--;
            }

            if(list.contains(c[Rindex])&& list.contains(c[Lindex])){
            char tmp = c[Rindex];
            c[Rindex]=c[Lindex];
            c[Lindex]=tmp;
            Rindex++;
            Lindex--;
            }
        }

        String result= new String (c);

        return result;  
    }
}

コード　listを使用 実行時間:10ms メモリー:45.10MB

class Solution {
    public String reverseVowels(String s) {
        char [] c = s.toCharArray();
        List<Character>list = new ArrayList<>();
        list.add('a');
        list.add('i');
        list.add('u');
        list.add('e');
        list.add('o');
        list.add('A');
        list.add('I');
        list.add('U');
        list.add('E');
        list.add('O');

        int Rindex=0, Lindex=c.length-1;
        while(Rindex < Lindex){
            if(!list.contains(c[Rindex])){
                Rindex++;
            }

            if(!list.contains(c[Lindex])){
                Lindex--;
            }

            if(list.contains(c[Rindex])&& list.contains(c[Lindex])){
            char tmp = c[Rindex];
            c[Rindex]=c[Lindex];
            c[Lindex]=tmp;
            Rindex++;
            Lindex--;
            }
        }

        String result= new String (c);

        return result;  
    }
}

理由

HashSetは重複する要素を含まないコレクションであり、その要素が特定の順序で存在しないからです。

Listの特徴

①順序や②重複がListでは実現できます。そのため、高パフォーマンスではなく①や②を重視する場合はListを使用した方がいいかもしれません。

参考