2

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?

Improve this question
7
  • 4
    How is 10 is 0th? Shouldn't it be 9th Commented Mar 23, 2017 at 9:14
  • 1
    @bureaquete That depends on whether the order is descending or ascending. The current lambda expression in the OP's code assumes descending order. Commented Mar 23, 2017 at 9:25
  • 1
    @Eran then how is 3 is 1st? His final array is {10, 3, 2, 5, 4, 1, 6, 7, 8, 9} Commented Mar 23, 2017 at 9:27
  • 3
    @bureaquete Where did you get {10, 3, 2, 5, 4, 1, 6, 7, 8, 9} from? His final array is {0, 3, 4, 9, 8, 1, 2, 5, 6, 7}. 0 is the index of 10 in the original array, 3 is the index of 9, 4 is the index of 8, and so on. Commented Mar 23, 2017 at 9:31
  • 1
    This code Arrays.sort(index, (a, b) -> (nums[b] - nums[a])); can fail if nums[b] is very large and nums[a] is a negative number. Integer overflow will rear its ugly head. See blog.mischel.com/2016/11/21/… Commented Mar 23, 2017 at 13:04

3 Answers 3

Reset to default
3

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]);
                       }
            });
Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

I do not get why this is getting down voted. It is what @saltmangotree asks for, isnt it?
I'd use Integer.compare (which is pre Java 8) considering the overflow issue with a naive subtraction.
@Eran, I understand the solution, but have a follow up question. When does the Comparator know when to stop the process of sorting. Is it when for the given array, which is index, it has ensured that for any two Integer a and b passed in, nums[b] is always greater than nums[a] ? What is the order of elements processed for a and b, does it check for all possible paits of a and b? Or is this determined by the sorting algorithm that Arrays.sort internally uses?
@saltmangotree The Comparator knows nothing. It's the sorting algorithm that makes these decisions. Any decent sorting algorithm doesn't check all possible pairs.
@Eran, can we rephrase that as follows : The Comparator knows nothing about which two elements are chosen and that is decided by the sorting algorithm. However, what the comparator does know is, given two elements, what should come before what. Am I right in saying so?
1

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;
}
Improve this answer

1 Comment

You solution using Comparator and overriding the compare method is clear to me. But I have a couple of questions regarding the internal working, if you could kindly answer. When does the Comparator know when to stop the process of sorting. Is it when for the given array, which is index, it has ensured that for any two Integer a and b passed in, nums[b] is always greater than nums[a] ? What is the order of elements processed for a and b, does it check for all possible paits of a and b? Or is this determined by the sorting algorithm that Arrays.sort internally uses?
0

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

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.