2012-08-17 10 views
9

私は配列をソートし、ソートされた順序で各要素のインデックスを探したいと思います。私は、アレイ上でこれを実行する場合 だから例えば:Javaで並べ替えの置換を見つける方法

[3,2,4] 

私が取得したい:

[1,0,2] 

は、Javaでこれを行う簡単な方法はありますか?

答えて

8

要素が配列に格納されているとします。

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ループ。

+0

グアバ-ER非常にクール! –

+0

私はGuavaの使用を全面的に拘束しました。私はあなたに知らせます;) –

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

しかし、問題は重複した要素はマップのキーでは許可されていません。 –

+0

@Shengyuan Luあなたは重複について正しいです。入力が{3,2,4,3,3}の場合、結果は[1,4,2]になり、ルイス・ワッサーマンの結果は[1,0,3,4,2]になります。 user491880が好きなのはどれですか? – rickz

1

これを達成する1つの方法は、開始インデックスを持つペアのリストをペアの2番目の部分として作成することです。辞書的にペアのリストをソートし、ソートされた配列から開始位置を読み込みます。

開始配列:

[3,2,4] 

が開始インデックスと対を追加:

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

lexicographically

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

各対の第二の部分を読み取るソート

[1,0,2] 
0
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 
    } 
} 
+0

データ範囲内の数値だけであることが既にわかっているようなケースを有効にします。 – BLUEPIXY

0

これは、ストリーム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(); 
} 

IntStreamには.sorted(IntComparator)方法、またはそのことについてもIntComparator機能インタフェースが存在しないように、それは幾分残念ながら、インデックスのボックス化とアンボックス化工程を必要とします。 ListComparableのオブジェクトに一般化する

は非常に簡単です:

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(); 
} 
関連する問題