Cerinta completa

You are given an unordered array of unique integers incrementing from . 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

The following arrays can be formed by swapping the 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 . If , we can swap to the highest possible value: .

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 and , the length of and the maximum swaps that can be performed.
The second line contains distinct space-separated integers from to as where .

Constraints


Output Format

Print the lexicographically largest permutation you can make with at most 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 and see the largest permutation is

Sample Input 1

3 1
2 1 3

Sample Output 1 

3 1 2

Explanation 1

With 1 swap we can get , and . Of these, is the largest permutation.

Sample Input 2

2 1
2 1

Sample Output 2 

2 1

Explanation 2

We can see that 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