Dadas dos arrays A y B de igual tamaño. La tarea es imprimir cualquier permutación de la array A tal que se maximice el número de índices i para los cuales A[i] > B[i] .
Ejemplos:
Input: A = [12, 24, 8, 32],
B = [13, 25, 32, 11]
Output: 24 32 8 12
Input: A = [2, 7, 11, 15],
B = [1, 10, 4, 11]
Output: 2 11 7 15
Si el elemento más pequeño de A vence al elemento más pequeño de B , debemos emparejarlos. De lo contrario, es inútil para nuestra puntuación, ya que no puede vencer a ningún otro elemento de B.
Con la estrategia anterior hacemos dos vectores de pares , Ap para A y Bp para B con su elemento y respectivo índice . Luego ordene ambos vectores y simulelos. Siempre que encontremos cualquier elemento en el vector Ap tal que Ap[i].primero > Bp[j].primero para algún (i, j)los emparejamos i:e actualizamos nuestra array de respuesta a ans[Bp[j].second] = Ap[i].first . Sin embargo, si Ap[i].primero < Bp[j].primero para algunos (i, j) , los almacenamos en vector y finalmente los emparejamos con cualquiera.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find permutation of an array that
// has smaller values from another array
#include <bits/stdc++.h>
using namespace std;
// Function to print required permutation
void anyPermutation(int A[], int B[], int n)
{
// Storing elements and indexes
vector<pair<int, int> > Ap, Bp;
for (int i = 0; i < n; i++)
Ap.push_back(make_pair(A[i], i));
for (int i = 0; i < n; i++)
Bp.push_back(make_pair(B[i], i));
sort(Ap.begin(), Ap.end());
sort(Bp.begin(), Bp.end());
int i = 0, j = 0, ans[n] = { 0 };
// Filling the answer array
vector<int> remain;
while (i < n && j < n) {
// pair element of A and B
if (Ap[i].first > Bp[j].first) {
ans[Bp[j].second] = Ap[i].first;
i++;
j++;
}
else {
remain.push_back(i);
i++;
}
}
// Fill the remaining elements of answer
j = 0;
for (int i = 0; i < n; ++i)
if (ans[i] == 0) {
ans[i] = Ap[remain[j]].first;
j++;
}
// Output required permutation
for (int i = 0; i < n; ++i)
cout << ans[i] << " ";
}
// Driver program
int main()
{
int A[] = { 12, 24, 8, 32 };
int B[] = { 13, 25, 32, 11 };
int n = sizeof(A) / sizeof(A[0]);
anyPermutation(A, B, n);
return 0;
}
// This code is written by Sanjit_Prasad
Java
// Java program to find permutation of an
// array that has smaller values from
// another array
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG{
// Function to print required permutation
static void anyPermutation(int A[], int B[], int n)
{
// Storing elements and indexes
ArrayList<int[]> Ap = new ArrayList<>();
ArrayList<int[]> Bp = new ArrayList<>();
for(int i = 0; i < n; i++)
Ap.add(new int[] { A[i], i });
for(int i = 0; i < n; i++)
Bp.add(new int[] { B[i], i });
// Sorting the Both Ap and Bp
Collections.sort(Ap, (x, y) -> {
if (x[0] != y[0])
return x[0] - y[0];
return y[1] - y[1];
});
Collections.sort(Bp, (x, y) -> {
if (x[0] != y[0])
return x[0] - y[0];
return y[1] - y[1];
});
int i = 0, j = 0;
int ans[] = new int[n];
// Filling the answer array
ArrayList<Integer> remain = new ArrayList<>();
while (i < n && j < n)
{
// Pair element of A and B
if (Ap.get(i)[0] > Bp.get(j)[0])
{
ans[Bp.get(j)[1]] = Ap.get(i)[0];
i++;
j++;
}
else
{
remain.add(i);
i++;
}
}
// Fill the remaining elements of answer
j = 0;
for(i = 0; i < n; ++i)
if (ans[i] == 0)
{
ans[i] = Ap.get(remain.get(j))[0];
j++;
}
// Output required permutation
for(i = 0; i < n; ++i)
System.out.print(ans[i] + " ");
}
// Driver Code
public static void main(String[] args)
{
int A[] = { 12, 24, 8, 32 };
int B[] = { 13, 25, 32, 11 };
int n = A.length;
anyPermutation(A, B, n);
}
}
// This code is contributed by Kingash
Python3
# Python3 program to find permutation of # an array that has smaller values from # another array # Function to print required permutation def anyPermutation(A, B, n): # Storing elements and indexes Ap, Bp = [], [] for i in range(0, n): Ap.append([A[i], i]) for i in range(0, n): Bp.append([B[i], i]) Ap.sort() Bp.sort() i, j = 0, 0, ans = [0] * n # Filling the answer array remain = [] while i < n and j < n: # pair element of A and B if Ap[i][0] > Bp[j][0]: ans[Bp[j][1]] = Ap[i][0] i += 1 j += 1 else: remain.append(i) i += 1 # Fill the remaining elements # of answer j = 0 for i in range(0, n): if ans[i] == 0: ans[i] = Ap[remain[j]][0] j += 1 # Output required permutation for i in range(0, n): print(ans[i], end = " ") # Driver Code if __name__ == "__main__": A = [ 12, 24, 8, 32 ] B = [ 13, 25, 32, 11 ] n = len(A) anyPermutation(A, B, n) # This code is contributed # by Rituraj Jain
Javascript
<script>
// JavaScript program to find permutation of
// an array that has smaller values from
// another array
// Function to document.write required permutation
function anyPermutation(A, B, n){
// Storing elements and indexes
let Ap = [], Bp = []
for(let i=0;i<n;i++){
Ap.push([A[i], i])
}
for(let i=0;i<n;i++){
Bp.push([B[i], i])
}
Ap.sort()
Bp.sort()
let i = 0
let j = 0
let ans = new Array(n).fill(0)
// Filling the answer array
let remain = []
while(i < n && j < n){
// pair element of A and B
if(Ap[i][0] > Bp[j][0]){
ans[Bp[j][1]] = Ap[i][0]
i += 1
j += 1
}
else{
remain.push(i)
i += 1
}
}
// Fill the remaining elements
// of answer
j = 0
for(let i=0;i<n;i++){
if(ans[i] == 0){
ans[i] = Ap[remain[j]][0]
j += 1
}
}
// Output required permutation
for(let i=0;i<n;i++){
document.write(ans[i]," ")
}
}
// Driver Code
let A = [ 12, 24, 8, 32 ]
let B = [ 13, 25, 32, 11 ]
let n = A.length
anyPermutation(A, B, n)
// This code is contributed by shinjanpatra
</script>
24 32 8 12
Complejidad de tiempo: O(N*log(N)), donde N es la longitud de la array.
Publicación traducida automáticamente
Artículo escrito por Sanjit_Prasad y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA