排列给定的小于O（n^2）的整数列表

Question

如何给给定的整数列表中的元素分配排名？ 是否有一个时间复杂度小于O（n^2）的算法？

Input: 2 6 7 3 9 
Output: 1 3 4 2 5 

Answer 1

您可以轻松地通过排序为此在O(n * log n)：

int[] input = //... 
int[] input = new int[]{2, 6, 7, 3, 9}; 
Integer[] indices = new Integer[input.length]; 
for (int i = 0; i < indices.length; i++) { 
    indices[i] = i; 
} 

// find permutation of indices that would yield sorted input 
Arrays.sort(indices, Comparator.comparingInt(i -> input[i])); 

// invert permutation and add 1 to get rank 
int[] ranks = new int[indices.length]; 
for (int i = 0; i < indices.length; i++) { 
    ranks[indices[i]] = i+1; 
}