java - 使用HashMap降低时间复杂度，还是有更好的方法？

Question

是的，这是我用来准备 1 月份考试的旧考试。我们给出了以下方法:

public static void Oorspronkelijk()
{
    String bs = "Dit is een boodschap aan de wereld";
    int max = -1;
    char let = '*';
    for (int i=0;i<bs.length();i++) {
        int tel = 1;
        for (int j=i+1;j<bs.length();j++) {
            if (bs.charAt(j) == bs.charAt(i)) tel++;
        }

        if (tel > max) {
            max = tel;
            let = bs.charAt(i);
        }
    }

    System.out.println(max + " keer " + let);
}

问题是:

1. 输出是什么？ - 由于代码只是一种确定出现次数最多的字符的算法，因此输出为“6 keer”(6 倍空间)
2. 这段代码的时间复杂度是多少？ 相当确定它是 O(n²)，除非有人不这么认为？
3. 你能降低时间复杂度吗？如果可以，怎么做？

嗯，你可以。我已经得到了一些帮助，并设法获得了以下代码:

public static void Nieuw()
{
    String bs = "Dit is een boodschap aan de wereld";
    HashMap<Character, Integer> letters = new HashMap<Character, Integer>();
    char max = bs.charAt(0);
    for (int i=0;i<bs.length();i++) {
        char let = bs.charAt(i);
        if(!letters.containsKey(let)) {
            letters.put(let,0);
        }

        int tel = letters.get(let)+1;
        letters.put(let,tel);

        if(letters.get(max)<tel) {
            max = let;
        }
    }

    System.out.println(letters.get(max) + " keer " + max);
}

但是，我不确定这段新代码的时间复杂度:它是 O(n) 因为你只使用一个 for 循环，还是我们需要使用 HashMap 的 get 方法这一事实使它成为 O( n log n) ?

如果有人知道降低时间复杂度的更好方法，请告诉我! :)

Answer 1

新代码的时间复杂度为 O(n) - 这是因为 hashmap 查找是一个常数时间操作，常数时间操作不影响顺序。

我可以提出的一个建议，只是一个优化(不会产生很大的不同)——不是一个重大的变化，也不会影响顺序——你可以使用一个整数数组而不是一个 HashMap 来跟踪每个字符的计数。只需使用与 char 等效的 int 值作为数组的索引。