排序后获取数组的索引？

Question

假设用户输入一个数组,例如:

Array = {France, Spain, France, France, Italy, Spain, Spain, Italy}

我确实知道它的长度

的index阵列将是:

index = {0, 1, 2, 3, 4, 5, 6, 7}

现在,使用后对其进行排序 Arrays.sort(Array);

newArray 将会像:

newArray = {France, France, France, Italy, Italy, Spain, Spain, Spain}

而newIndex将是:

newIndex = {0, 2, 3, 4, 7, 1, 5, 6}

问题是:如何newIndex从输入数组中找到？

提前致谢

Answer 1

不要对数组进行排序.对索引数组进行排序,传入比较器,该比较器使用它们作为数组的索引来比较值.所以你最终newIndex得到了排序的结果,从那里到实际项目的排序数组是微不足道的.

不可否认,这意味着以自定义方式对整数数组进行排序 - 这意味着使用Integer[]标准Java库,或者具有"IntComparator"接口的第三方库,该接口可以与一种sort(int[], IntComparator)方法结合使用.

编辑:好的,这是一个示例比较器.为了简单起见,我假设您只想对"原始"字符串数组进行排序......而且我不会为无效测试而烦恼.

public class ArrayIndexComparator implements Comparator<Integer>
{
    private final String[] array;

    public ArrayIndexComparator(String[] array)
    {
        this.array = array;
    }

    public Integer[] createIndexArray()
    {
        Integer[] indexes = new Integer[array.length];
        for (int i = 0; i < array.length; i++)
        {
            indexes[i] = i; // Autoboxing
        }
        return indexes;
    }

    @Override
    public int compare(Integer index1, Integer index2)
    {
         // Autounbox from Integer to int to use as array indexes
        return array[index1].compareTo(array[index2]);
    }
}

你会这样使用它:

String[] countries = { "France", "Spain", ... };
ArrayIndexComparator comparator = new ArrayIndexComparator(countries);
Integer[] indexes = comparator.createIndexArray();
Arrays.sort(indexes, comparator);
// Now the indexes are in appropriate order.

Answer 2

使用Java 8 Stream API实现此目的的简明方法,

final String[] strArr = {"France", "Spain", "France"};
int[] sortedIndices = IntStream.range(0, strArr.length)
                .boxed().sorted((i, j) -> strArr[i].compareTo(strArr[j]) )
                .mapToInt(ele -> ele).toArray();

Answer 3

TreeMap<String,Int> map = new TreeMap<String,Int>();
for( int i : indexes ) {
    map.put( stringarray[i], i );
}

现在迭代map.values()以按排序顺序检索索引,并通过map.keySet()获取字符串,或通过map.entrySet()获取String-index-Pairs.

Answer 4

如果有重复对具有正值的原始 float 或 int 数组进行排序的场景，那么与使用任何比较器相比，像下面这样的方法会产生更好的 (x3~x4) 速度：

long time = System.currentTimeMillis();
for (int i = 0; i < iters; i++) {           
    float[] array = RandomUtils.randomFloatArray(-1,  1, 3000);
    long[] valueKeyPairs = new long[array.length]; 
    for (int j = 0; j < array.length; ++j) {
        valueKeyPairs[j] = (((long) Float.floatToIntBits(array[j])) << 32) | (j & 0xffffffffL);
    }
    Arrays.sort(valueKeyPairs);
    /**Then use this to retrieve the original value and index*/
    //long l = valueKeyPairs[j];
    //float value = Float.intBitsToFloat((int) (l >> 32));
    //int index = (int) (l);
}
long millis = System.currentTimeMillis() - time;