How to find the rank of each element in an integer array

Question

I want to know the rank of each element in an array, starting at 0.

For example:

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

Explanation:

 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 

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

Someone gave me a solution for this in the comments section below, but his comment was deleted. I do not know how to do that. Which works correctly for negative integers and positive integers, as well as a very large list size.

Thanks to the author

 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

So, with rank do you mean the position at which this element would end after sorting the array?

You can start by matching the identifiers map = {0,1,2} and then sort it, but using arr as the sort key.

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

This way you will not change your original array, but get a mapping from the elements of the array to its rank.

Obviously, this algorithm depends on the complexity of your sorting algorithm. You should get O (n log n), but maybe your data allows you to use sorting algorithms with O (n) complexity. But it really depends on what you keep on your long list.

Answer 2

first sort all the elements and save in another array (if the elements are not sorted) then print the index of the element from this array.

Answer 3

Use radix sort to sort the array in linear time. Each element will be in its own rank.

Answer 4

I give an idea. If you want, you can use this:

 It applicable if array value[0....n-1] 

• First, create a count_array from the input array of the counting sort technique (Ex: array = {2, 1, 3}, So count_array = {0,1,1,1} // here, use array value as count_array index value ).
• Then you can filter count_array as result_array = {0, 1, 2, 3} // only add 1 with previous added value if count_array[i] == 1 (you can also do this in count_array . I use result _array just for understanding )
• Then you do rank_array from result_array By rank_array[i] = result_array[array[i]] - 1
• Finally, you can find rank_array with O(n)

Example:

 array = {2,1,3} count_array = {0,1,1,1} result_array = {0,1,2,3} rank_array = {1,0,2} //rank_array[i] = result_array[array[i]] - 1 

Answer 5

in java 8, the first array is for a list, then for a stream. due to only one loop in the stream, it must be O (n).

 Integer[] arr = {2, 1,3 }; List <Integer> list = Arrays.asList(arr); Integer[] outArr = list.stream() .sorted() .map(e -> list.indexOf(e)) .toArray(Integer[]::new); 

Result: {1,0,2}

Answer 6

You can use a map to map an index in an array to a value, sort values ​​and return indexes. It might look like this:

 private static int[] ranks(int[] array) { Map<Integer, Integer> m = new HashMap<> (); for (int i = 0; i < array.length; i++) { m.put(i, array[i]); } return m.entrySet().stream() .sorted(Entry.comparingByValue()) .mapToInt(Entry::getKey) .toArray(); } 

Usage example:

 int[] ranks = ranks(new int[] { 2, 1, 3 }); System.out.println(Arrays.toString(ranks)); //outputs {1, 0, 2} 

Answer 7

You can calculate this rank using a data structure called the "Order Statistics Tree", this is an extended data structure. To implement this structure, you must implement a balanced binary tree (for example, AVL-Tree or Red-Black Tree), and you add an additional attribute to each node. This is a very efficient way to calculate ranks because each element requires O (lg n) (where lg is the logarithm of base 2). You can find more information about this data structure in the chapter "Introduction to Algorithms" in chapter 14.

The problem with sorting is that its runtime is O (nlog (n)), and I think it is inefficient if you want to rank multiple elements (i.e. less than n elements).