CODEWITHSUNDEEP
javaarrays
Amr Gamal
Amr Gamal

Reputation: 23

arrangement of arrays indices from minimum to maximum

I want to take the arrangement of numbers in array from minimum value to maximum value. For example if I insert 5 16 4 12 26 and I stored them in array [5,16,4,12,26], I want to order array from minimum to maximum and store the indexes in array like this [1,3,0,2,4]

Integer [] key = {5,16,4,12,26};
Integer [] orderedkey = key.clone();
Arrays.sort(orderedkey);
List <Integer> x = Arrays.asList(orderedkey);
for (int i = 0; i < x.size(); i++) {
    System.out.println(x.indexOf(i))
}

Upvotes: 2

Views: 72

Answers (2)

fps
fps

Reputation: 34460

Using List.indexOf() within a [1..n] for loop is O(n^2). If n is not too big, this is OK.

However, there's another approach which is O(nlogn):

Integer[] key = { 5, 16, 4, 12, 26 };

TreeMap<Integer, Integer> orderedKey = new TreeMap<>();
for (int i = 0; i < key.length; i++) {
    orderedKey.put(key[i], i);
}
List<Integer> x = new ArrayList<>(orderedKey.values());

TreeMap<Integer, Integer> orderedIndexes = new TreeMap<>();
for (int i = 0; i < x.size(); i++) {
    orderedIndexes.put(x.get(i), i);
}

List<Integer> result = new ArrayList<>(orderedIndexes.values());

System.out.println(result); // [1, 3, 0, 2, 4]

This solution relies on Java's TreeMap, which is a map that keeps its entries ordered by its keys natural order.

Two TreeMaps are needed to accomplish what you want. The first one would map the values to their indexes, while the second one would map the indexes of the ordered values to a range [1..n].

As both maps are ordered by its keys, when we ask for its values() to the second map, we get the indexes in the desired ordered.

Upvotes: 0

Hollis Waite
Hollis Waite

Reputation: 1079

You could put items in sorted set and then count number of predecessors. This only works if values are unique.

final Integer[] key = {5, 16, 4, 12, 26};
final NavigableSet<Integer> set = new TreeSet<>(Arrays.asList(key));
final Integer[] orderedKey = new Integer[key.length];
for (int i = 0; i < key.length; i++) {
    orderedKey[i] = set.headSet(key[i]/*, true*/).size();
}
System.out.println(Arrays.toString(orderedKey));

Upvotes: 1

Related Questions