Java - 在字符串中查找第一个重复字符的最佳方法是什么

Question

我写了下面的代码来检测字符串中的第一个重复字符。

public static int detectDuplicate(String source) {
    boolean found = false;
    int index = -1;
    final long start = System.currentTimeMillis();
    final int length = source.length();
    for(int outerIndex = 0; outerIndex < length && !found; outerIndex++) {
        boolean shiftPointer = false;
        for(int innerIndex = outerIndex + 1; innerIndex < length && !shiftPointer; innerIndex++ ) {
            if ( source.charAt(outerIndex) == source.charAt(innerIndex)) {
                found = true;
                index = outerIndex;
            } else {
                shiftPointer = true;
            }
        }
    }
    System.out.println("Time taken --> " + (System.currentTimeMillis() - start) + " ms. for string of length --> " + source.length());
    return index;
}

我在两件事上需要帮助:

• 这个算法在最坏情况下的复杂度是多少？ - 我的理解是 O(n)。
• 这是最好的方法吗？有人可以提供更好的解决方案(如果有的话)吗？

谢谢，神经元

Answer 1

正如其他人所提到的，您的算法是 O(n^2)。这是一个 O(N) 算法，因为 HashSet#add 在恒定时间内运行(散列函数将元素适本地分散在桶中)——请注意，我最初将散列集的大小设置为最大大小以避免调整大小/重新散列:

public static int findDuplicate(String s) {
    char[] chars = s.toCharArray();
    Set<Character> uniqueChars = new HashSet<Character> (chars.length, 1);
    for (int i = 0; i < chars.length; i++) {
        if (!uniqueChars.add(chars[i])) return i;
    }
    return -1;
}

注意:这将返回第一个重复项的索引(即与前一个字符重复的第一个字符的索引)。要返回该字符第一次出现的索引，您需要将索引存储在 Map<Character, Integer> 中。 (在这种情况下 Map#put 也是 O(1)):

public static int findDuplicate(String s) {
    char[] chars = s.toCharArray();
    Map<Character, Integer> uniqueChars = new HashMap<Character, Integer> (chars.length, 1);
    for (int i = 0; i < chars.length; i++) {
        Integer previousIndex = uniqueChars.put(chars[i], i);
        if (previousIndex != null) {
            return previousIndex;
        }
    }
    return -1;
}