如何在Java中找到排序的排列
我想对数组进行排序,并按排序顺序查找每个元素的索引。 例如,如果我在数组上运行它:
[3,2,4]
我得到:
[1,0,2]
在Java中有一种简单的方法吗?
我们假设您的元素存储在一个数组中。
final int[] arr = // elements you want List indices = new ArrayList (arr.length); for (int i = 0; i < arr.length; i++) { indices.add(i); } Comparator comparator = new Comparator () { public int compare(Integer i, Integer j) { return Integer.compare(arr[i], arr[j]); } } Collections.sort(indices, comparator);
现在, indices
按其排序顺序包含数组的索引。 您可以使用简单的for
循环将其转换回int[]
。
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())); } }
实现此目的的一种方法是将具有起始索引的对列表作为该对的第二部分。 按字典顺序对对列表进行排序,然后从排序的数组中读取起始位置。
启动数组:
[3,2,4]
添加具有起始索引的对:
[(3,0), (2,1), (4,2)]
按字典顺序排序
[(2,1), (3,0), (4,2)]
然后读掉每对的第二部分
[1,0,2]
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
作为更新,使用流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)
上没有.sorted(IntComparator)
方法,甚至IntComparator
function接口也没有。
要概括为Comparable
对象List
非常简单:
public static > int[] sortedPermutation(final List 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(); }