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

实现此目的的一种方法是制作一个配对列表，其中起始索引作为配对的第二部分。按字典顺序对对列表进行排序，然后从排序后的数组中读取起始位置。

起始数组：

[3,2,4]

添加具有起始索引的对：

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

按字典顺序排序

[(2,1), (3,0), (4,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

作为更新，在 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功能接口。

推广到 a ListofComparable对象非常简单：

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