Problem Statement
A permutation p[0], p[1], ..., p[n-1] is a sequence containing each number from 0 to n-1 exactly once. The result of applying permutation p to an array a of length n is an array b of length n, where b[p[i]] = a[i] (0-based indices).
Given an array a, find a permutation which has the effect of sorting the elements of a in non-descending order, i.e., an order where each element is greater than or equal to the previous one. If there are several suitable permutations return the lexicographically smallest one.
The permutation p[0], p[1], ..., p[n-1] is considered lexicographically smaller than the permutation q[0], q[1], ..., q[n-1] if there is an index i such that p[i] < q[i] and the equation p[j] = q[j] holds for all j < i.
Given an array a, find a permutation which has the effect of sorting the elements of a in non-descending order, i.e., an order where each element is greater than or equal to the previous one. If there are several suitable permutations return the lexicographically smallest one.
The permutation p[0], p[1], ..., p[n-1] is considered lexicographically smaller than the permutation q[0], q[1], ..., q[n-1] if there is an index i such that p[i] < q[i] and the equation p[j] = q[j] holds for all j < i.
Definition
- Class:
- SortingWithPermutation
- Method:
- getPermutation
- Parameters:
- int[]
- Returns:
- int[]
- Method signature:
- int[] getPermutation(int[] a)
- (be sure your method is public)
Constraints
- a will contain between 1 and 50 elements, inclusive.
- Each element of a will be between 1 and 1000, inclusive.
Examples
{2, 3, 1}Returns: {1, 2, 0 }The element that is originally at position 0 goes to position 1. The elements originally at positions 1 and 2 go to positions 2 and 0, respectively.{2, 1, 3, 1}Returns: {2, 0, 3, 1 }There are two suitable permutations - {2, 0, 3, 1} and {2, 1, 3, 0}. The first one is lexicographically smaller.{4, 1, 6, 1, 3, 6, 1, 4}Returns: {4, 0, 6, 1, 3, 7, 2, 5 }
Back to all problems