java - 如何获取由原始字符串保留顺序的所有唯一字符组成的字符串？

Question

给定一个字符串输入:

aaabbbcccdddeee

Output should be:

abcde

How I made this program?

Given an input String, I have sorted the characters of this String in ascending order using bubble sort [no need for efficient algorithm now] and then removed duplicates.

But the problem is that I cannot apply this approach on a string string like bbkjhiaa, as it changes the order of my original string.

I need to code this using concepts of array and string only.

class SingleOccurence
{
    static String singleoccurence(String p)
    {
        char current = ch[0];
        boolean found = false; //what is the use of boolean variable 
        for (int i = 0; i < ch.length; i++) 
        {
            if (current == ch[i] && !found) 
            {
                found = true;  
            }
            else if (current != ch[i])
            {
                System.out.print(current);
                current = ch[i];
                found = false;
            }
        }
        System.out.println(current);
        String s4=new String(ch);
        return s4;   
    }
    public static void main(String s[])
    {  
        String s1=new String("qwwnniitootiinn");
        String s6=SortingDemo.bubble1(s1);
        String s5=singleoccurence(s6);   
    }
}

Answer 1

事实上，对字符串进行排序是不可能的，因为这可能会改变输入。

您需要做的是将整个字符串放入一个数组中，然后从头到尾迭代该数组。始终记住上次访问的值并与其进行比较。如果我们现在考虑的值与之前的值相同，则跳过它，否则显示它。

public static String deDuplicate(char[] inpt) {
    Set<Character> already_seen_chars = new HashSet<Character>();
    String result = "";

    for(int i = 0; i < inpt.length; i++) {
        if(!already_seen_chars.contains(inpt[i])) { // Is the character already contained in the set?
            result += Character.toString(inpt[i]);
            already_seen_chars.add(inpt[i]);
        }
    }

    return result;
}

public static void main(String[] args) {
    String test = "ttttteeeeesssstttt";
    System.out.println(deDuplicate(test.toCharArray()));
}

输入:qwwnniitootiinn，输出:qwnito

请注意，性能也比以前更好，O(n) 而不是 O(n^2)(其中 n 是字符串的长度)。

编辑:如果您不允许使用 Set 数据结构，您可以用 for 循环替换 mySet.contains(...) ，该循环遍历字符串并检查字符。

这给出:

public static String deDuplicate(String input) {
    char[] inpt = input.toCharArray();
    String result = "";

    for(int i = 0; i < inpt.length; i++) {
        if(!contains(inpt, inpt[i], i)) { // Is the character already contained in the set?
            result += Character.toString(inpt[i]);
        }
    }

    return result;
}

contains 函数是:

public static boolean contains(char[] inpt, char c, int maxIndex) {
    for(int i = 0; (i < inpt.length) && (i < maxIndex); i++) {
        if(inpt[i] == c)
            return true;
    }

    return false;
}

请注意，这会影响性能! deDuplicate 中的 for 循环现在调用 contains，后者也包含一个 for 循环。因此导致 O(n^2) 性能。