CODEWITHSUNDEEP
javaalgorithmsortinglambdajava-8
saltmangotree
saltmangotree

Reputation: 171

Getting rank of element upon sorting the array

I am given an array, and I would like to find the position of these elements in the sorted version of the array. So, the input and output would look like as follows

Input : {10, 5, 4, 9, 8, 3, 2, 1,  6, 7}
Output: {0, 3, 4, 9, 8, 1, 2, 5, 6, 7}

This means that, 10 would be at 0th position in the sorted array, and 5, would be in the fourth index, ie sortedinput[3].

Here is a one-liner which does it

Arrays.sort(index, (a, b) -> (nums[b] - nums[a]));

The method would look as follows

public Integer[] findIndexInSortedArray(int[] nums) {
        Integer[] index = new Integer[nums.length];

        for (int i = 0; i < nums.length; i++) {
            index[i] = i;
        }

        Arrays.sort(index, (a, b) -> (nums[b] - nums[a]));

        return index;
}

Is there a way, to do the same as above, without using lambdas, and any of the features of Java 8? Is it possible to achieve this, using only a Comparator?

Upvotes: 2

Views: 961

Answers (3)

d4u7
d4u7

Reputation: 29

The Comparator<T> Interface is a FunctionalInterface and marked as one with the annotation @FunctionalInterface.

Since Java 8 you can use FunctionalInterfaces with Lambda expressions as you did it in the Arrays.sort method.

The Expression can be replaced with a anonymous inner class and the Code is blowing up but the result is the same:

public Integer[] findIndexInSortedArray(int[] nums)
{
    Integer[] index = new Integer[nums.length];

    for (int i = 0; i < nums.length; i++)
    {
        index[i] = i;
    }

    Arrays.sort(index, new Comparator<Integer>()
        {
            @Override
            public int compare(Integer a, Integer b)
            {
                return nums[b] - nums[a];
            }
        });

    return index;
}

Upvotes: 1

Aziuth
Aziuth

Reputation: 3902

Basic idea:

  1. write your own sorting algorithm
  2. at the beginning of the sorting algorithm, create an array that has the same size as the array that is to be sorted and is filled with 0,1,2,3,...
  3. adjust your sorting algorithm so that every time it performs an action on the array to be sorted, it does the same action on the new array
  4. return the new array instead of the array to be sorted

To elaborate on step 3: If you'd use bubble sort, for example, every time you swap an element i and j within the array to be sorted, you swap the elements in the new array with the same indices

Upvotes: 0

Eran
Eran

Reputation: 393811

A lambda expression can always be replaced by the functional interface it implements (Comparator<Integer> in your case). It just takes longer to write:

Arrays.sort(index, new Comparator<Integer> () {
                       public int compare (Integer a, Integer b) {
                           return Integer.compare(nums[b],nums[a]);
                       }
            });

Upvotes: 3

Related Questions