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

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

これを実現する 1 つの方法は、ペアの 2 番目の部分として開始インデックスを持つペアのリストを作成することです。ペアのリストを辞書順で並べ替え、並べ替えられた配列から開始位置を読み取ります。

開始配列:

[3,2,4]

開始インデックスを持つペアを追加します。

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

辞書順に並べ替えます

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

次に、各ペアの 2 番目の部分を読み取ります

[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

更新として、ストリーム API を使用して Java 8 でこれを行うのは比較的簡単です。

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)です.IntStreamIntComparator

オブジェクトの aListに一般化するのは非常に簡単です。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();
}