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

发布时间：2020-12-14 23:21:16 所属栏目：Java 来源：网络整理

导读：我写了下面的代码来检测字符串中的第一个重复字符. 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

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

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).
>这是最好的方法吗？有人可以提供更好的解决方案(如果有的话)吗？

谢谢,
NN

解决方法

正如其他人所提到的,你的算法是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;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!