Jak znaleźć permutację sortowania w Javie?

Question

Chcę posortować tablicę i znaleźć indeks każdego elementu w posortowanej kolejności. Tak na przykład, jeśli uruchomię to na tablicy:

[3,2,4] 

bym dostać:

[1,0,2] 

Czy istnieje prosty sposób to zrobić w Java?

Answer 1

Załóżmy, że twoje elementy są przechowywane w tablicy.

final int[] arr = // elements you want 
List<Integer> indices = new ArrayList<Integer>(arr.length); 
for (int i = 0; i < arr.length; i++) { 
    indices.add(i); 
} 
Comparator<Integer> comparator = new Comparator<Integer>() { 
    public int compare(Integer i, Integer j) { 
    return Integer.compare(arr[i], arr[j]); 
    } 
} 
Collections.sort(indices, comparator); 

Teraz indices zawiera indeksy tablicy w uporządkowanej kolejności. Możesz przekonwertować to z powrotem na int[] z prostą pętlą for.

Answer 2

import java.util.*; 
public class Testing{ 
    public static void main(String[] args){ 
     int[] arr = {3, 2, 4, 6, 5}; 
     TreeMap map = new TreeMap(); 
     for(int i = 0; i < arr.length; i++){ 
      map.put(arr[i], i); 
     } 
     System.out.println(Arrays.toString(map.values().toArray())); 
    } 
} 

Answer 3

Jednym ze sposobów osiągnięcia tego jest utworzenie listy par z indeksem początkowym jako drugiej części pary. Posortuj listę par leksykograficznie, a następnie odczytaj pozycje początkowe z posortowanej tablicy.

początkowy tablicy:

[3,2,4] 

Dodawanie par indeksami wyjściowego:

[(3,0), (2,1), (4,2)] 

układać lexicographically

[(2,1), (3,0), (4,2)] 

następnie odczytuje się z drugiej części z każdej pary

[1,0,2] 

Answer 4

import java.io.*; 

public class Sample { 
    public static void main(String[] args) { 
     int[] data = {0, 3, 2, 4, 6, 5, 10};//case:range 0 - 10 
     int i, rangeHigh = 10; 
     int [] rank = new int[rangeHigh + 1]; 
     //counting sort 
     for(i=0; i< data.length ;++i) ++rank[data[i]]; 
     for(i=1; i< rank.length;++i) rank[i] += rank[i-1]; 
     for(i=0;i<data.length;++i) 
      System.out.print((rank[data[i]]-1) + " ");//0 2 1 3 5 4 6 
    } 
} 

Answer 5

Aktualizacja jest stosunkowo łatwa w Java 8 przy użyciu API strumieni.

public static int[] sortedPermutation(final int[] items) { 
    return IntStream.range(0, items.length) 
    .mapToObj(value -> Integer.valueOf(value)) 
    .sorted((i1, i2) -> Integer.compare(items[i1], items[i2])) 
    .mapToInt(value -> value.intValue()) 
    .toArray(); 
} 

To nieco niestety wymaga boks i unboxing krok dla indeksów, ponieważ nie ma .sorted(IntComparator) metoda na IntStream lub nawet IntComparator funkcjonalny interfejs dla tej sprawy.

Uogólniając Do List z Comparable obiektów jest dość prosta:

public static <K extends Comparable <? super K>> int[] sortedPermutation(final List<K> items) { 
    return IntStream.range(0, items.size()) 
    .mapToObj(value -> Integer.valueOf(value)) 
    .sorted((i1, i2) -> items.get(i1).compareTo(items.get(i2))) 
    .mapToInt(value -> value.intValue()) 
    .toArray(); 
}