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

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

首先对所有元素进行排序并存储在另一个数组中（如果元素未排序），然后打印该数组中的元素索引。