Largest Permutation Javascript Solution
Largest Permutation Solution
from hackerrank.com
Problem:
You are given an array of integers which is a permutation of the first natural numbers. You can swap any two elements of the array. You can make at most swaps. What is the largest permutation, in numerical order, you can make?
Input Format
The first line of the input contains two integers, and , the size of the input array and the maximum swaps you can make, respectively. The second line of the input contains a permutation of the first natural numbers.
Output Format
Print the lexicographically largest permutation you can make with at most swaps.
Solution in Javascript
function swap(list, index1,index2){
//console.log('SWAP '+index1 +' with index '+index2);
var b = list[index2];
list[index2] = list[index1];
list[index1] = b;
}
function processData(input) {
input = input.split('\n');
let list = input[1].split(' ').map(Number);
let n = parseInt(input[0].split(' ')[0]);
let k = parseInt(input[0].split(' ')[1]);
let result_list = [];
let j = 0;
let list_index = [];
//console.log('List is '+list);
for(let i=0; i<n; i++){
//console.log(i, list[i]);
list_index[list[i]] = i;
}
let exitMainLoop = false;
// console.log('List Index is '+list_index);
while (k--) {
//console.log('K is '+k);
for(let i=j;i<n;i++){
//console.log('i = '+i+' j= '+j);
//console.log('List[i] = '+list[i]);
//console.log('n-i ='+(n-i));
if(list[i]!==n-i){
let temp = list_index[n-i];
//console.log('Temp is '+temp);
let t = list_index[list[i]];
//console.log('list_index before swapping is '+list_index);
swap(list_index,list[i],list[temp]);
//console.log('list_index after swapping is '+list_index);
//console.log('list before swapping is '+list);
swap(list,i,temp);
//console.log('list after swapping is '+list);
break;
}
// console.log('In order to avoid timeouts we should exit main While loop as soon we have finished swapping all elements');
if(i>n-2){
exitMainLoop = true;
}
}
if(exitMainLoop){
break;
}
j++;
}
console.log(list.join(' '));
}
process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
_input += input;
});
process.stdin.on("end", function () {
processData(_input);
});
Σχόλια