java - 在不使用额外缓冲区的情况下删除重复项

Question

我编写了一个简单的程序来从字符串中删除重复项，而无需使用任何额外的缓冲区。有人可以告诉我这是否是一个好的解决方案吗？我只想知道是否有比以下解决方案更好的其他解决方案..

编辑：如果我传入“跟进”作为输入，我应该取回唯一的字符串“FW UP”

    public static void removeDuplicateString(String input) {
        String value1 = input;
        String value2 = input;
        String finalValue = "";
        int count = 0;
        char char1;
        char char2;
        for (int i = 0; i < value1.length(); i++) {
            char1 = value1.charAt(i);
            for (int j = 0; j < value2.length(); j++) {
                char2 = value2.charAt(j);
                if (char1 == char2) {
                    count++;
                }
            }
            if (count > 1) {
                //System.out.println(i);
            } else {
                finalValue = finalValue + char1;
            }

            count = 0;
        }
        System.out.println(finalValue);
    }

}

Answer 1

如何使用这样的基于正则表达式的正则表达式从给定的字符串中删除重复字符：

String nonDup = input.replaceAll("(.)(?=.*?\\1)", "");

现场演示：http: //ideone.com/W7EaPq

Answer 2

您的解决方案有效。

另一种解决方案：

public static void removeDuplicateString2(String input) {
    wh:
    while(true)
    {
        for(char c : input.toCharArray())
        {
            if(input.contains("" + c + c))
            {
                input = input.replaceAll("["+ c +"]" + "["+ c +"]", "");
                continue wh;
            }
        }
        break;
    }

    System.out.println(input);
}

丑陋但有效。

Answer 3

你可以试试这个：

public String removeDuplicateChars(String inputString) {
        if (inputString.length() <= 1 ) {
            return inputString;
        }
        if(inputString.substring(1, 2).equals(inputString.substring(0, 1)) ) {
            return removeDuplicateChars(inputString.substring(1));
        } else {
            return inputString.substring(0, 1) + removeDuplicateChars(inputString.substring(1));
        }
    }

Answer 4

public 你可以试试这个：

   public static void removeDuplicateString(String input) {
        char[] ch = input.toCharArray();
        char[] copy = new char[ch.length];
        char[] avoid = new char[ch.length];
        int counter = 0,count=0;
        for (int i = 0 ; i < ch.length; i++)
        {
            char cch = ch[i];
            boolean duplicate = false;
            if (input.indexOf(cch)==i && input.indexOf(cch,i+1)==-1)
            {
                for (int j = 0 ; j <=count ; j++)
                {
                    if (avoid[i]==cch)
                    {
                        duplicate = true;
                        break;
                    }
                }
                if (!duplicate)
                {
                    copy[counter] = cch;
                    counter++;
                }
            }
            else
            {
                avoid[count] = cch;
                count++;
            }
        }
        String finalString = new String(copy,0,counter);
        System.out.println(finalString);
    }

Answer 5

您可以使用“Mergesort”或“Quicksort”（假设您可以在排序时使用临时数组来分配数据，则需要额外的“O(n)”空间来执行此操作）。

对数组进行排序后，您可以简单地遍历数组，将一个元素与以下元素进行比较，每次发现给定元素等于同一个元素时，将元素向后移动一个位置。

通过这样做，你有：

• O(N LOG N) 因为排序
• O(N) 遍历所有元素
• O(M) 向后移动元素

根据重复的数量，此代码可能会变得非常慢，因为向后移动元素以擦除重复的成本。