如何在java中优化两个for循环（for循环中的for循环）

Question

我有以下问题：

• 我有一个很长的字符串String str = "abcdefghiart----"
• 现在我想迭代字符串，并想找到字符串中的第一个重复字符
• 我可以通过应用两个for循环来搜索第一个副本来实现这一点

• 这种方法工作得很好，但如果字符串非常大，并且只有最后两个字符是重复的，那么迭代的复杂性将非常高

  现在我想最小化复杂性并优化代码。我也可以使用foreach循环进行迭代，但仍然是两个foreach循环。我不想使用任何系统库。有人能帮我吗

Answer 1

BitSet seenCharacters = new BitSet();
for(int i=0;i<str.length(); i++) {
  if(seenCharacters.get(str.charAt(i))) {
    return str.charAt(i); // duplicate
  }
  seenCharacters.set(i);
}

。。。够简单了吧

Answer 2

我会用不同的解决方案来解决这个问题。我将使用一个hashmap（或它的任何衍生物），键将是一个字符，值将为null

然后我将遍历字符串，每次获取一个字符，对于每个字符，我将尝试向hashmap插入一个条目。如果插入失败，则我知道该字符（即密钥本身）是重复的

Answer 3

定义一个大小为[26]的整数数组，每个字母表有一个插槽

遍历字符串，并针对每个字母表检查插槽的值是否为>；如果是0，那么对应于插槽的字母表就是重复字符，如果是0，只需增加它并继续前进

Answer 4

下面是一个查找字符串中第一个重复字符的方法

 public static String findFirstDuplicate(String string){

                 for(int i=0;i<string.length()-1; i++){
                     String c=string.charAt(i)+"";
                     if(string.indexOf(c, i+1)>-1)
                         return  c;
                 }

                 return null;
  }

至于优化，您可以通过自定义合并排序来优化它，以查找重复值，并在找到重复值时终止。这里的解释有点复杂，但在最坏的情况下，使用改进的合并排序算法，您将能够在O（nlogn）中找到第一个副本