Sort list based on first occurance of elements-CodePudding

I have a Java List<Integer> with a collection of values, containing for example:

[0, 5, 2, 1, 3, 2, 6, 1, 1, 0, 10]

I want to sort the list by the first occurrence of each element, with the following newly sorted list:

[0, 0, 5, 2, 2, 1, 1, 1, 3, 6, 10]

The List I am dealing with be max 400-500 elements, so something lightweight is preferred but I can't quite figure out an approach.

CodePudding user response：

I think there is even simplier solution with usage of LinkedHashMap, which remembers put order:

    List<Integer> source = Arrays.asList(0, 5, 2, 1, 3, 2, 6, 1, 1, 0, 10);
    List<Integer> target = new ArrayList<>();

    Map<Integer, Integer> map = new LinkedHashMap<>();
    source.forEach(number -> map.merge(number, 1, Integer::sum));

    map.forEach((key, value) -> {
        for (int i = 0; i < value; i  ) {
            target.add(key);
        }
    });

    System.out.println(target);

CodePudding user response：

You can directly sort by using the result of indexOf (which returns the first index of an element in the list).

List<Integer> list = Arrays.asList(0, 5, 2, 1, 3, 2, 6, 1, 1, 0, 10);
list.sort(Comparator.comparingInt(list::indexOf));
System.out.println(list);

Demo

CodePudding user response：

You need 2 data structures:

a Map to store how many times a number occured
a List to remember in which order they occurred

This code does what you want:

String in = "0, 5, 2, 1, 3, 2, 6, 1, 1, 0, 10";
String[] split = in.split(", ");
List<Integer> lstIn = Arrays.stream(split).map(Integer::parseInt).collect(Collectors.toList());
Map<Integer, Integer> theMap = new HashMap<>();
List<Integer> listOccurence = new LinkedList<>();

for(Integer i:lstIn) {
    theMap.compute(i, (k,v)->v==null?1:v 1);
    if(!listOccurence.contains(i)) {
        listOccurence.add(i);
    }
}
List<Integer> out = new LinkedList<>();
for(Integer i:listOccurence) {
    Integer count = theMap.get(i);
    for(int j=0;j<count;j  ) {
        out.add(i);
    }
}
System.out.println(out);

This prints:

[0, 0, 5, 2, 2, 1, 1, 1, 3, 6, 10]