删除字符串中的重复项而不使用数组

String input = "AAAB"; 

    String output = ""; 
    for (int index = 0; index < input.length(); index++) { 
     if (input.charAt(index % input.length()) != input 
       .charAt((index + 1) % input.length())) { 

      output += input.charAt(index); 

     } 
    } 
    System.out.println(output);

但是，如果我的输入是“ABABAB”或只是“AAAA”，则不起作用。有任何想法吗？删除字符串中的重复项而不使用数组

来源

2012-12-13 Mosaab

我并不完全相信你的意图是什么，你可以添加输入和匹配预期输出的例子吗？ – bowmore

您需要定义：*不使用数组*。 'input.charAt（..）'正在使用一个数组，例如... – assylias

使用一个数据结构来知道，如果一个角色已经被发现，如Set。例如，您可以使用其add()方法并检查其返回值。

此外，您可以考虑使用StringBuilder对于重复拼接，这是更有效的。

Set<Character> characters = new HashSet<Character>(); 
String input = "AAAB"; 
StringBuilder output = new StringBuilder(); 
for (int index = 0; index < input.length(); index++) { 
    char character = input.charAt(index); 
    if (characters.add(character)) { 
     output.append(character); 
    } 
} 
System.out.println(output.toString());

来源

2012-12-13 18:23:11

具有讽刺意味的是使用数组会更困难。 – Esailija

这是一个好主意，但我不允许使用任何类型的数组，我的意思是hashset也是如此。 – Mosaab

（我希望你的意思是重复的，不重复。）

public static String withoutDuplicates(String s) { 
    for (int i = 0; i < s.length();) { 
     boolean removedDuplicate = false; 
     for (int duplicateLength = (s.length() - i)/2; duplicateLength >= 1; 
       --duplicateLength) { 
      if (foundDuplicate(s, i, duplicateLength)) { 
       s = s.substring(0, i) + s.substring(i + duplicateLength); 
       removedDuplicate = true; 
       break; 
      } 
     } 
     if (!removedDuplicate) { 
      ++i; 
     } 
    } 
    return s; 
} 

private static boolean foundDuplicate(String s, int i, int duplicateLength) { 
    String sought = s.substring(i, i + duplicateLength); 
    return s.indexOf(sought, i + duplicateLength) != -1; 
}

更正： duplicateLength初始化值超出范围。

来源

2012-12-13 18:45:38

非常感谢:) – Mosaab

但是当我使用ABCCDA时出现错误。 – Mosaab

这应该成为BCDA（因为总是删除第一个副本）。 –

优化了极速版

public static void main(String[] args) { 
    String input = "AAAB"; 
    StringBuilder output = new StringBuilder(); 
    for (int i = 0; i < input.length(); i++) { 
     if (!contains(output, input.charAt(i))) { 
      output.append(input.charAt(i)); 
     } 
    } 
    System.out.println(output); 
} 

private static boolean contains(StringBuilder output, char c) { 
    for(int i = 0; i < output.length(); i++) { 
     if (output.charAt(i) == c) { 
      return true; 
     } 
    } 
    return false; 
}

来源

2012-12-13 18:47:37

考虑到“contains”方法，这不是O（n（log n））吗？使用'HashSet的＃加（）'（O（1）），并通过串去（为O（n））是O（n） –

这个程序与原始字符才有效。你能想象为每个char创建一个Object的成本吗？没有测试，我可以说差异将是巨大的。 –

实际上，从[5.1.7]开始装箱时，似乎''u0000'-'\ u007f'范围内的字符被缓存。拳击转换]（http://docs.oracle.com/javase/specs/jls/se7/html/jls-5.html#jls-5.1.7）。但绝对是一个好点。作为一个方面说明，正如@assylias在他的评论中指出的那样，使用StringBuilder来搜索字符可以被看作是使用数组。但是再次，几乎所有流行的数据结构（如'HashSet' /'Map'）最终都使用了数组:) –

让我们来看看你的循环是这样做的：

if (input.charAt(index % input.length()) != input 
    .charAt((index + 1) % input.length()))

1）首先，你应该意识到，你就是在浪费时间和处理能力通过执行'％input.length（）'操作，因为索引总是小于input.length（），所以index％input.length（）总是等于索引。

让我们无视％input.length（）前进。

2）当你比较input.charAt（index）来input.charAt（索引+ 1）你只是比较反对下一个当前字符。原来的问题，如果我理解正确的话，会要求你删除所有重复的东西，而不仅仅是那些相邻的东西。 3）你的算法很可能会抛出IndexOutOfBounds异常，因为当你到达字符串的末尾时（当index == input.length（） - 1）时，检查input.charAt（index + 1）将看起来是一个字符在字符串中太远了。

作为第一个答案的建议，你会想使用某种形式的数据结构来存储所有你遇到了性格迥异的。任何时候你点击一个新角色，你都会想要a）将它添加到你的数据结构中，并且b）将它添加到你的输出结尾。

来源

2012-12-13 18:49:29

他使用模数只是为了避免100B。在这种情况下，最好让它发生，因为他将最后一个字符与第一个字符进行比较。 –

是的，我做到了，因为我想看看最后一个元素==第一个元素。 – Mosaab

public static void print(String s) { 
    List<String> v = new ArrayList<String>(); 
    for(int j=0; j<s.length(); j++) { 
     if(!v.contains("" + s.charAt(j))) 
      v.add("" + s.charAt(j)); 
    } 


    for(String e : v) 
     System.out.print(e); 
}

来源

2012-12-13 18:54:22 pgardunoc

对不起，我删除了前一个，是的，前面的代码是因为TreeSet而打印的，这个保留了原始的顺序。 – pgardunoc

删除字符串中的重复项而不使用数组

回答

相关问题