Problem Statement
We once had a permutation of the numbers from 0 to N-1, inclusive.
Then, someone erased some of its elements (possibly none or all of them). The order of the remaining elements was preserved.
You are given the sequence that remained in the int[] partial.
Reconstruct and return the original permutation. If there are multiple options, return the lexicographically smallest one among them.
Definition
- Class:
- ReconstructPermutation
- Method:
- reconstruct
- Parameters:
- int, int[]
- Returns:
- int[]
- Method signature:
- int[] reconstruct(int N, int[] partial)
- (be sure your method is public)
Notes
- Given two distinct permutations of order N, the one that has a smaller value at the first index at which they differ is lexicographically smaller.
Constraints
- N will be between 1 and 500, inclusive.
- Each element of partial will be between 0 and N-1, inclusive.
- All elements of partial will be mutually distinct.
Examples
8
{1, 3, 5, 7}Returns: {0, 1, 2, 3, 4, 5, 6, 7 }The given partial permutation can be obtained from the lexicographically smallest of all permutations, so that is the answer.5
{3, 1, 4, 0, 2}Returns: {3, 1, 4, 0, 2 }Nothing is missing, the input permutation is also the correct output.5
{0, 3, 1}Returns: {0, 2, 3, 1, 4 }There are 20 different permutations from which the given partial permutation could have been obtained. The other 19 are all lexicographically greater than the one shown as correct return value.8
{}Returns: {0, 1, 2, 3, 4, 5, 6, 7 }