Как найти перестановку рода в Java

Question

Я хочу отсортировать массив и найти индекс каждого элемента в отсортированном порядке. Так, например, если я запускаю это в массиве:

[3,2,4]

Я бы получил:

[1,0,2]

Есть ли простой способ сделать это на Java?

Answer 1

Давайте предположим, что ваши элементы хранятся в массиве.

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);

Сейчас indices содержит индексы массива в их отсортированном порядке. Вы можете преобразовать это обратно в int[] с достаточно простым for петля.

Answer 2

Одним из способов достижения этого является составление списка пар с начальным индексом в качестве второй части пары. Сортируйте список пар лексикографически, затем считывайте начальные позиции из отсортированного массива.

Начальный массив:

[3,2,4]

Добавьте пары с начальными индексами:

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

Сортировать это лексикографически

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

затем прочитайте вторую часть каждой пары

[1,0,2]

Answer 3

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 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

В качестве обновления это относительно легко сделать в Java 8 с помощью API потоков.

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();
}

В некоторой степени, к сожалению, требуется выполнить этапы упаковки и распаковки для индексов, поскольку .sorted(IntComparator) метод на IntStreamили даже IntComparator функциональный интерфейс в этом отношении.

Обобщать на List из Comparable Объекты довольно просты:

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();
}