1

に 1 回だけ出現する文字列の数を見つけようとしていますArrayList。

これを何回達成できますか (可能な限り最高の時間計算量で)。

以下は私の方法です：

  public static int countNonRepeats(WordStream words) {

    ArrayList<String> list = new ArrayList<String>();
    for (String i : words) {
      list.add(i);
    }

    Collections.sort(list);

    for (int i = 1; i < list.size(); i++) {
      if (list.get(i).equals(list.get(i - 1))) {
        list.remove(list.get(i));
        list.remove(list.get(i - 1));
      }
    }

    System.out.println(list);

    return list.size();
  }

list.get(i)との文字列を削除しないのはなぜlist.get(i-1)ですか?

4

4 に答える 4

3

並べ替える必要はありません。より良いアプローチは、2 つの HashSet 1 を繰り返しを維持するために使用し、もう 1 つを繰り返しのない単語に使用することです。HashSet は内部的に HashMap を使用するため、理想的には、contains、get、put 操作は o(1) の複雑さを持ちます。したがって、このアプローチの全体的な複雑さは o(n) になります。

    public static int countNonRepeats(List<String> words) {

    Set<String> nonRepeating = new HashSet<String>();
    Set<String> repeating = new HashSet<String>();


    for (String i : words) {
        if(!repeating.contains(i)) {
            if(nonRepeating.contains(i)){
                repeating.add(i);
                nonRepeating.remove(i);
            }else {
                nonRepeating.add(i);
            }
        }
    }

    System.out.println(nonRepeating.size());

    return nonRepeating.size();
}
于 2016-03-14T19:48:48.347 に答える
2

簡単な提案を次に示します。

  1. まず、配列を英数字順に並べ替えます
  2. ループで繰り返し、if( !list.get(i).equals(list.get(i+1)) ) → unique
  3. 重複が見つかった場合はi、別の文字列に到達するまでインクリメントします

ステップ 2+3 は O(n) である必要があるため、これにはソート アルゴリズムの複雑さが伴います。

于 2016-03-14T19:18:52.477 に答える
0

ハッシュマップを使用してこれを実現できます。このアプローチでは、すべての単語の出現をカウントできます。
一意の単語のみに関心がある場合は、カウント = 1 の要素にアクセスします。
HashMap<String,Integer>- キーは arraylist の文字列を表し、整数はカウントを表します。発生の。

        ArrayList<String> list = new ArrayList<String>();
        HashMap<String, Integer> hashMap = new HashMap<String, Integer>();

        for (int i = 0; i < list.size(); i++) {

            String key = list.get(i);

            if (hashMap.get(key) != null) {
                int value = hashMap.get(key);
                value++;
                hashMap.put(key, value);
            } else {
                    hashMap.put(key, 1);
            }

        }
        int uniqueCount = 0;
        Iterator it = hashMap.entrySet().iterator();
        while (it.hasNext()) {
            Map.Entry pair = (Map.Entry) it.next();
            if ((int) pair.getValue() == 1)
                uniqueCount++;
        }
        System.out.println(uniqueCount);
于 2016-03-14T19:48:40.833 に答える