如何找到整数数组中每个元素的等级 [英] How to find what is the rank of each element in an integer array

问题描述

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

I want to find out the rank of each element in an array starting from 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）的算法。

What I have tried is n^2 time complexity algorithm. I want an algorithm with linear time complexity O(n).

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

Someone gave me solution for it in the comment section below but his comment has been deleted I don't know how. Which is correctly working for negative integers and positive integers as well as very large size of list.

感谢作者

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))
    }
}

推荐答案

因此，对于排名，您指的是排序数组后此元素结束的位置？

So with rank you mean the position where this element would end up after sorting the array?

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

You can start with a identity mapping map = {0,1,2} and then sort that, but using your arr as sort key.

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

这样你就不会改变原始数组，而是从数组元素到它的数组元素的映射排名。

This way you won't change your original array, but get a mapping from your array elements to its rank.

显然，这种算法取决于排序算法的复杂性。
您应该以O（n log n）结束，但也许您的数据允许使用具有O（n）复杂度的排序算法。但这实际上取决于你在大名单中存储的内容。

Obviously this algorithm depends on the complexity of your sort algorithm. You should end up with O(n log n) but maybe your data allows to use sorting algorithms with O(n) complexity. But that really depends on what you store in your big list.

这篇关于如何找到整数数组中每个元素的等级的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！