用于删除字符串中重复字符的函数 [英] function to remove duplicate characters in a string

问题描述

以下代码尝试删除字符串中的任何重复字符。我不确定代码是否正确。任何人都可以帮我处理代码（即当字符匹配时实际发生了什么事情）？

The following code is trying to remove any duplicate characters in a string. I'm not sure if the code is right. Can anybody help me work with the code (i.e whats actually happening when there is a match in characters)?

public static void removeDuplicates(char[] str) {
  if (str == null) return;
  int len = str.length;
  if (len < 2) return;
  int tail = 1;
  for (int i = 1; i < len; ++i) {
    int j;
    for (j = 0; j < tail; ++j) {
      if (str[i] == str[j]) break;
    }
    if (j == tail) {
      str[tail] = str[i];
      ++tail;
    }
  }
  str[tail] = 0;
}

推荐答案

考虑到以下问题：

编写代码以使用任何其他缓冲区删除字符串中没有
的重复字符。注意：一个或两个额外的变量
没问题。数组的额外副本不是。

Write code to remove the duplicate characters in a string without using any additional buffer. NOTE: One or two additional variables are fine. An extra copy of the array is not.

由于一个或两个附加变量很好但不允许缓冲区，因此可以使用整数来存储位来模拟散列映射的行为。这个简单的解决方案在O（n）运行，比你的速度快。此外，它在概念上并不复杂和就地：

Since one or two additional variables are fine but no buffer is allowed, you can simulate the behaviour of a hashmap by using an integer to store bits instead. This simple solution runs at O(n), which is faster than yours. Also, it isn't conceptually complicated and in-place :

    public static void removeDuplicates(char[] str) {
        int map = 0;
        for (int i = 0; i < str.length; i++) {
            if ((map & (1 << (str[i] - 'a'))) > 0) // duplicate detected
                str[i] = 0;
            else // add unique char as a bit '1' to the map
                map |= 1 << (str[i] - 'a');
        }
    }

缺点是副本（替换为0（））不会放在str []数组的末尾。但是，这可以通过最后一次循环遍历数组来轻松解决。此外，整数只能容纳普通字母。

The drawback is that the duplicates (which are replaced with 0's) will not be placed at the end of the str[] array. However, this can easily be fixed by looping through the array one last time. Also, an integer has the capacity for only regular letters.

这篇关于用于删除字符串中重复字符的函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！