java - 如何找到整数数组中每个元素的等级

Question

我想找出从0开始的数组中每个元素的排名。

例如:

arr = {2, 1,3 } 
rank will be {1,0 ,2}

解释:

rank of 2 is 1 because 2 is greater than exactly 1 element
rank of 1 is 0 because 1 is greater than exactly  0  element
rank of 3 is 2 because 1 is greater than exactly  2  element

我试过的是n^2时间复杂度算法。我想要一个具有线性时间复杂度 O(n) 的算法。

有人在下面的评论部分给了我解决方案，但他的评论已被删除我不知道如何。这适用于负整数和正整数以及非常大的列表。

感谢作者

import java.io.IOException;
import java.io.InputStream;
import java.util.*;

class rank{
    public static void main(String args[]){
        ArrayList<Integer> list = new ArrayList<Integer>();
        list.add(2);
        list.add(1);
        list.add(3);
        ArrayList<Integer> listCopy = new ArrayList<Integer>(list);

        Collections.sort(list); // sorting array
         //   System.out.println("List : " + listCopy);
         //  System.out.println("Sorted List : " + list);

        Map<Integer, Integer> rankMap = new HashMap<Integer, Integer>();
        int counter = 0;
        for(int x : list) {
            rankMap.put(x, counter); 
            // list value as key and rank as  value.
            counter++;
        }
        StringBuffer sb=new StringBuffer();
        for(int x : listCopy) {
            sb.append(rankMap.get(x) + " "); 
            // System.out.println(map.get(x));
        }
        System.out.println( sb.toString().substring(0, sb.length()-1))
    }
}

Answer 1

那么对于 rank 你的意思是这个元素在数组排序后结束的位置？

您可以从标识映射 map = {0,1,2} 开始，然后对其进行排序，但使用您的 arr 作为排序键。

Collections.sort(map, (c1, c2) -> arr[c2] > arr[c1] ? +1 : arr[c2] == arr[c1] ? 0 : -1);

这样您就不会更改原始数组，而是获得从数组元素到其排名的映射。

显然，此算法取决于排序算法的复杂性。 您应该以 O(n log n) 结束，但也许您的数据允许使用复杂度为 O(n) 的排序算法。但这实际上取决于您在大列表中存储的内容。