Soluție HackerRank pentru Largest Permutation. Include cerința formatată, exemple, explicația pașilor și cod sursă.

  • Problemă: Largest Permutation

Cerinta completa

You are given an unordered array of unique integers incrementing from [Expresie matematică indisponibilă în copia arhivată]. You can swap any two elements a limited number of times. Determine the largest lexicographical value array that can be created by executing no more than the limited number of swaps.

Example
[Expresie matematică indisponibilă în copia arhivată]
[Expresie matematică indisponibilă în copia arhivată]

The following arrays can be formed by swapping the [Expresie matematică indisponibilă în copia arhivată] with the other elements: 

[2,1,3,4]
[3,2,1,4]
[4,2,3,1]

The highest value of the four (including the original) is [Expresie matematică indisponibilă în copia arhivată]. If [Expresie matematică indisponibilă în copia arhivată], we can swap to the highest possible value: [Expresie matematică indisponibilă în copia arhivată].

Function Description

Complete the largestPermutation function in the editor below. It must return an array that represents the highest value permutation that can be formed.

largestPermutation has the following parameter(s):

  • int k: the maximum number of swaps
  • int arr[n]: an array of integers

Input Format

The first line contains two space-separated integers [Expresie matematică indisponibilă în copia arhivată] and [Expresie matematică indisponibilă în copia arhivată], the length of [Expresie matematică indisponibilă în copia arhivată] and the maximum swaps that can be performed.
The second line contains [Expresie matematică indisponibilă în copia arhivată] distinct space-separated integers from [Expresie matematică indisponibilă în copia arhivată] to [Expresie matematică indisponibilă în copia arhivată] as [Expresie matematică indisponibilă în copia arhivată] where [Expresie matematică indisponibilă în copia arhivată].

Constraints

[Expresie matematică indisponibilă în copia arhivată]
[Expresie matematică indisponibilă în copia arhivată]

Output Format

Print the lexicographically largest permutation you can make with at most [Expresie matematică indisponibilă în copia arhivată] swaps.
Sample Input 0 

STDIN       Function
-----       --------
5 1         n = 5, k = 1
4 2 3 5 1   arr = [4, 2, 3, 5, 1]

Sample Output 0 

5 2 3 4 1

Explanation 0

You can swap any two numbers in [Expresie matematică indisponibilă în copia arhivată] and see the largest permutation is [Expresie matematică indisponibilă în copia arhivată]

Sample Input 1

3 1
2 1 3

Sample Output 1 

3 1 2

Explanation 1

With 1 swap we can get [Expresie matematică indisponibilă în copia arhivată], [Expresie matematică indisponibilă în copia arhivată] and [Expresie matematică indisponibilă în copia arhivată]. Of these, [Expresie matematică indisponibilă în copia arhivată] is the largest permutation.

Sample Input 2

2 1
2 1

Sample Output 2 

2 1

Explanation 2

We can see that [Expresie matematică indisponibilă în copia arhivată] is already the largest permutation. We don’t make any swaps.

Limbajul de programare folosit: java8

Cod:

import java.util.Arrays;
import java.util.Map;
import java.util.Scanner;
import java.util.function.Function;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Solution {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		int k = sc.nextInt();
		int[] a = new int[n];
		for (int i = 0; i < a.length; i++) {
			a[i] = sc.nextInt();
		}

		System.out.println(Arrays.stream(solve(a, k)).mapToObj(String::valueOf).collect(Collectors.joining(" ")));

		sc.close();
	}

	static int[] solve(int[] a, int k) {
		Map<Integer, Integer> numberToIndex = IntStream.range(0, a.length).boxed()
				.collect(Collectors.toMap(i -> a[i], Function.identity()));

		int index = 0;
		for (int i = 0; i < k; i++) {
			while (index < a.length && a[index] == a.length - index) {
				index++;
			}

			if (index == a.length) {
				break;
			}

			swap(a, numberToIndex, index, numberToIndex.get(a.length - index));
			index++;
		}

		return a;
	}

	static void swap(int[] a, Map<Integer, Integer> numberToIndex, int index1, int index2) {
		int number1 = a[index1];
		int number2 = a[index2];

		a[index1] = number2;
		a[index2] = number1;

		numberToIndex.put(number1, index2);
		numberToIndex.put(number2, index1);
	}
}

Scor obtinut: 1.0

Submission ID: 464603183

Link challenge: https://www.hackerrank.com/challenges/largest-permutation/problem

Largest Permutation