sort array of characters in the order of occurrence within a string

Question

If I have an array of characters filled with characters, and I have a String initialized with some initial value, then how can I make sure that the characters in the array are sorted in the order of occurents of how they appear within the string.

You can make the following additional assumptions:

unused characters should appear at the end in their original order.
if multiple occurrences of the same character occur within the array, they can refer to the same occurrence within the string.

Example, assume following two initialized variables:

char [] arr= new char[5] { 'a', 'd', 'v', 'd', 'j' };
String str = "dad";

Then the expected result would be that the variable arr would have sorted the characters as follows:

{ 'd', 'a', 'd', 'v', 'j' }

For what ultimate goal? What would be the purpose of doing this? Showing your coding attempt may answer these questions but for some reason, I doubt it. — DevilsHnd - 退した
– DevilsHnd - 退した, Commented Jan 17, 2017 at 6:17
An Open letter to students with homework problems for students and those who might answer them — AxelH
– AxelH, Commented Jan 17, 2017 at 6:58

Maurice Perry · Accepted Answer · 2017-01-17 07:27:33Z

1

Here is a possible solution:

public static void main(String[] args) throws IOException  {
    char [] arr= { 'a', 'd', 'v', 'd', 'j' };
    String str = "dad";
    int pos = 0;
    for (char c: str.toCharArray()) {
        int i = locate(c, arr, pos);
        if (i >= 0) {
            char x = arr[pos];
            arr[pos] = arr[i];
            arr[i] = x;
            ++pos;
        }
    }
    System.out.println(toString(arr));
}

private static int locate(char c, char[] arr, int start) {
    for (int i = start; i < arr.length; ++i) {
        if (arr[i] == c) {
            return i;
        }
    }
    return -1;
}

UPDATE: the toString method

private static String toString(char[] arr) {
    StringBuilder buf = new StringBuilder();
    buf.append('{');
    boolean first = true;
    for (char c: arr) {
        if (first) {
            first = false;
        } else {
            buf.append(',');
        }
        buf.append(c);
    }
    buf.append('}');
    return buf.toString();
}

UPDATE 2: to preserve the order of the elements that are not in the string.

        if (i >= 0) {
            char x = arr[i];
            for (int k = pos; k < i; ++k) {
                char y = arr[k];
                arr[k] = x;
                x = y;
            }
            arr[i] = x;
            ++pos;
        }

edited Jan 17, 2017 at 7:27

answered Jan 17, 2017 at 6:50

Maurice Perry

9,6782 gold badges15 silver badges28 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Sid Over a year ago

Where does the toString come from? Did you mean to use Arrays.toString() ?

Sid Over a year ago

Ok, you don't need to do that, Arrays.toString() will take care of it. The solution works, btw. I would try and find a functional solution with no mutations. Just out of curiosity. Thanks.

SubOptimal Over a year ago

If I right understand the requirement of the OP, then your solution is wrong for input {'a','d','v','x','d','j'}. The output should be {d,a,d,v,x,j} instead of {d,a,d,x,v,j}.

Community · Accepted Answer · 2017-05-23 11:53:11Z

I wrote this solution which (partially) solves the problem.

    String source = "pippo";
    Comparator<Character> comparator = new Comparator<Character>() {

        private int countChar(String s, char c) {
            return s.length() - s.replace(Character.toString(c), "").length();
        }
        @Override
        public int compare(Character o1, Character o2) {
            return countChar(source, o2) - countChar(source, o1);
        }
    };
    Character[] charObjectArray = source.chars().mapToObj(c -> (char)c).toArray(Character[]::new);
    Arrays.sort(charObjectArray , comparator);

What is still missing is the implementation of this feature:

if multiple occurrences of the same character occur within the array, they can refer to the same occurrence within the string.

The method to count occurrences of char in a String was found here: https://stackoverflow.com/a/8910767/379173

Collectives™ on Stack Overflow

sort array of characters in the order of occurrence within a string

2 Answers 2

3 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related