Index related sorting problem in Java

This is the requirement where I am facing 开发者_如何学运维problem finding the solution.

Problem:

I have ArrayList with data 20, 10, 30, 50, 40, 10.

If we sort this in ascending order the result will be 10, 10, 20, 30, 40, 50.

But I need the result as 3, 1, 4, 6, 5, 2.(The index of each element after sorting).

Strictly this should work even if there are repetitive elements in the list.

Please share your idea/approach solving this problem.

Here is my solution. We define a comparator to sort a list of indices based on the corresponding object in the list. That gives us a list of indices which is effectively a map: indices[i] = x means that the element at location x in the original list is at element i in the sorted list. We can then create a reverse mapping easily enough.

Output is the indices starting from 0: [2, 0, 3, 5, 4, 1]

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

class LookupComparator<T extends Comparable<T>> implements Comparator<Integer> {
    private ArrayList<T> _table;
    public LookupComparator(ArrayList<T> table) { 
        _table = table; 
    }
    public int compare(Integer o1, Integer o2) {
        return _table.get(o1).compareTo(_table.get(o2));
    }
}

public class Test {

    public static <T extends Comparable<T>> ArrayList<Integer> indicesIfSorted(ArrayList<T> list) {
        ArrayList<Integer> indices = new ArrayList<Integer>();
        for (int i = 0; i < list.size(); i++)
            indices.add(i);
        Collections.sort(indices, new LookupComparator(list));

        ArrayList<Integer> finalResult = new ArrayList<Integer>();
        for (int i = 0; i < list.size(); i++)
            finalResult.add(0);
        for (int i = 0; i < list.size(); i++)
            finalResult.set(indices.get(i), i);
        return finalResult;
    }

    public static void main(String[] args) {

        ArrayList<Integer> list = new ArrayList<Integer>();
        list.add(20);
        list.add(10);
        list.add(30);
        list.add(50);
        list.add(40);
        list.add(10);

        ArrayList<Integer> indices = indicesIfSorted(list);
        System.out.println(indices);


    }


}

My idea is creating 1 more attribute call index beside your value (in each data of aray). It will hold your old index, then u can take it out for using.

Building off what Hury said, I think the easiest way I can see to do this is to make a new data type that looks something like:

public class Foo {
    private Integer value;
    private int origPosition;
    private int sortedPosition;
    /*Constructors, getters, setters, etc... */
}

And some psuedo code for what to do with it...

private void printSortIndexes(ArrayList<Integer> integerList) {
    // Create an ArrayList<Foo> from integerList - O(n)
    // Iterate over the list setting the origPosition on each item - O(n)
    // Sort the list based on value
    // Iterate over the list setting the sortedPosition on each item - O(n)
    // Resort the list based on origPositon
    // Iterate over the lsit and print the sortedPositon - O(n)
}

That won't take long to implement, but it is horribly inefficient. You are throwing in an extra 4 O(n) operations, and each time you add or remove anything from your list, all the positions stored in the objects are invalidated - so you'd have to recaculate everything. Also it requires you to sort the list twice.

So if this is a one time little problem with a small-ish data set it will work, but if you trying to make something to use for a long time, you might want to try to think of a more elegant way to do it.

Here is the approach of adding an index to each element, written out in Scala. This approach makes the most sense.

list.zipWithIndex.sortBy{ case (elem, index) => elem }
  .map{ case (elem, index) => index }

In Java you would need to create a new object that implements comperable.

class IndexedItem implements Comparable<IndexedItem> {
    int index;
    int item;

    public int compareTo(IndexItem other) {
        return this.item - other.item;
    }
}

You could then build a list of IndexedItems, sort it with Collection.sort, and then pull out the indices.

You could also use Collections.sort on the original list followed by calls to indexOf.

for (int elem : originalList) {
    int index = newList.indexOf(elem);
    newList.get(index) = -1; // or some other value that won't be found in the list
    indices.add(index);
}

This would be very slow (all the scans of indexOf), but would get the job done if you only need to do it a few times.

A simplistic approach would be to sort the list; then loop on the original list, find the index of the element in the sorted list and insert that into another list.

so a method like

public List<Integer> giveSortIndexes(List<Integer> origList) {
    List<Integer> retValue = new ArrayList<Integer>();
    List<Integer> originalList = new ArrayList<Integer>(origList);
    Collections.sort(origList);
    Map<Integer, Integer> duplicates = new HashMap<Integer, Integer>();
    for (Integer i : originalList) {
        if(!duplicates.containsKey(i)) {
            retValue.add(origList.indexOf(i) + 1);
            duplicates.put(i, 1);
        } else {
            Integer currCount = duplicates.get(i);
            retValue.add(origList.indexOf(i) + 1 + currCount);
            duplicates.put(i, currCount + 1);
        }
    }
    return retValue;
}

I haven't tested the code and it might need some more handling for duplicates.