Dadas dos arrays ordenadas A[] y B[] de tamaño N , la tarea es verificar si es posible fusionar dos arrays ordenadas dadas en una nueva array ordenada de modo que no haya dos elementos consecutivos de la misma array.
Ejemplos:
Entrada: A[] = {3, 5, 8}, B[] = {2, 4, 6}
Salida: SíExplicación: array combinada = {B[0], A[0], B[1], A[1], B[2], A[2]}
Dado que la array resultante es una array ordenada, el resultado requerido es Sí.Entrada: A[] = {12, 4, 2, 5, 3}, B[] = {32, 13, 43, 10, 8}
Salida: No
Enfoque: siga los pasos a continuación para resolver el problema:
- Inicialice una variable, diga flag = true para verificar si es posible formar una nueva array ordenada al fusionar las dos arrays ordenadas dadas de modo que no haya dos elementos consecutivos de la misma array.
- Inicialice una variable, diga prev para verificar si el elemento anterior de la array de combinación es de la array A[] o la array B[] . Si prev == 1 entonces el elemento anterior es de la array A[] y si prev == 0 entonces el elemento anterior es de la array B[] .
- Recorra ambos arreglos usando las variables i y j y verifique las siguientes condiciones:
- Si A[i] < B[j] y prev != 0 entonces incremente el valor de i y actualice el valor de prev a 0 .
- Si B[j] < A[i[ y prev != 1 entonces incremente el valor de j y actualice el valor de prev a 1 .
- Si A[i] == B[j] y prev != 1 entonces incremente el valor de j y actualice el valor de prev a 1 .
- Si A[i] == B[j] y prev != 0 entonces incremente el valor de i y actualice el valor de prev a 0 .
- Si ninguna de las condiciones anteriores satisface, actualice flag = false .
- Finalmente, imprima el valor de la bandera .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if it is possible to merge
// the two given arrays with given conditions
bool checkIfPossibleMerge(int A[], int B[], int N)
{
// Stores index of
// the array A[]
int i = 0;
// Stores index of
// the array B[]
int j = 0;
// Check if the previous element are from
// the array A[] or from the array B[]
int prev = -1;
// Check if it is possible to merge the two
// given sorted arrays with given conditions
int flag = 1;
// Traverse both the arrays
while (i < N && j < N) {
// If A[i] is less than B[j] and
// previous element are not from A[]
if (A[i] < B[j] && prev != 0) {
// Update prev
prev = 0;
// Update i
i++;
}
// If B[j] is less than A[i] and
// previous element are not from B[]
else if (B[j] < A[i] && prev != 1) {
// Update prev
prev = 1;
// Update j
j++;
}
// If A[i] equal to B[j]
else if (A[i] == B[j]) {
// If previous element
// are not from B[]
if (prev != 1) {
// Update prev
prev = 1;
// Update j
j++;
}
// If previous element is
// not from A[]
else {
// Update prev
prev = 0;
// Update i
i++;
}
}
// If it is not possible to merge two
// sorted arrays with given conditions
else {
// Update flag
flag = 0;
break;
}
}
return flag;
}
// Driver Code
int main()
{
int A[3] = { 3, 5, 8 };
int B[3] = { 2, 4, 6 };
int N = sizeof(A) / sizeof(A[0]);
if (checkIfPossibleMerge(A, B, N)) {
cout << "Yes";
}
else {
cout << "No";
}
return 0;
}
Java
// Java program to implement
// the above approach
import java.io.*;
class GFG{
// Function to check if it is possible to merge
// the two given arrays with given conditions
static boolean checkIfPossibleMerge(int[] A, int[] B,
int N)
{
// Stores index of
// the array A[]
int i = 0;
// Stores index of
// the array B[]
int j = 0;
// Check if the previous element are from
// the array A[] or from the array B[]
int prev = -1;
// Check if it is possible to merge the two
// given sorted arrays with given conditions
boolean flag = true;
// Traverse both the arrays
while (i < N && j < N)
{
// If A[i] is less than B[j] and
// previous element are not from A[]
if (A[i] < B[j] && prev != 0)
{
// Update prev
prev = 0;
// Update i
i++;
}
// If B[j] is less than A[i] and
// previous element are not from B[]
else if (B[j] < A[i] && prev != 1)
{
// Update prev
prev = 1;
// Update j
j++;
}
// If A[i] equal to B[j]
else if (A[i] == B[j])
{
// If previous element
// are not from B[]
if (prev != 1)
{
// Update prev
prev = 1;
// Update j
j++;
}
// If previous element is
// not from A[]
else
{
// Update prev
prev = 0;
// Update i
i++;
}
}
// If it is not possible to merge two
// sorted arrays with given conditions
else
{
// Update flag
flag = false;
break;
}
}
return flag;
}
// Driver Code
public static void main(String[] args)
{
int[] A = { 3, 5, 8 };
int[] B = { 2, 4, 6 };
int N = A.length;
if (checkIfPossibleMerge(A, B, N))
{
System.out.println("Yes");
}
else
{
System.out.println("No");
}
}
}
// This code is contributed by akhilsaini
Python3
# Python3 program to implement
# the above approach
# Function to check if it is possible
# to merge the two given arrays with
# given conditions
def checkIfPossibleMerge(A, B, N):
# Stores index of
# the array A[]
i = 0
# Stores index of
# the array B[]
j = 0
# Check if the previous element
# are from the array A[] or from
# the array B[]
prev = -1
# Check if it is possible to merge
# the two given sorted arrays with
# given conditions
flag = 1
# Traverse both the arrays
while (i < N and j < N):
# If A[i] is less than B[j] and
# previous element are not from A[]
if (A[i] < B[j] and prev != 0):
# Update prev
prev = 0
# Update i
i += 1
# If B[j] is less than A[i] and
# previous element are not from B[]
elif (B[j] < A[i] and prev != 1):
# Update prev
prev = 1
# Update j
j += 1
# If A[i] equal to B[j]
elif (A[i] == B[j]):
# If previous element
# are not from B[]
if (prev != 1):
# Update prev
prev = 1
# Update j
j += 1
# If previous element is
# not from A[]
else:
# Update prev
prev = 0
# Update i
i += 1
# If it is not possible to merge two
# sorted arrays with given conditions
else:
# Update flag
flag = 0
break
return flag
# Driver Code
if __name__ == '__main__':
A = [ 3, 5, 8 ]
B = [ 2, 4, 6 ]
N = len(A)
if (checkIfPossibleMerge(A, B, N)):
print("Yes")
else:
print("No")
# This code is contributed by akhilsaini
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to check if it is possible to merge
// the two given arrays with given conditions
static bool checkIfPossibleMerge(int[] A, int[] B,
int N)
{
// Stores index of
// the array A[]
int i = 0;
// Stores index of
// the array B[]
int j = 0;
// Check if the previous element are
// from the array A[] or from the
// array B[]
int prev = -1;
// Check if it is possible to merge
// the two given sorted arrays with
// given conditions
bool flag = true;
// Traverse both the arrays
while (i < N && j < N)
{
// If A[i] is less than B[j] and
// previous element are not from A[]
if (A[i] < B[j] && prev != 0)
{
// Update prev
prev = 0;
// Update i
i++;
}
// If B[j] is less than A[i] and
// previous element are not from B[]
else if (B[j] < A[i] && prev != 1)
{
// Update prev
prev = 1;
// Update j
j++;
}
// If A[i] equal to B[j]
else if (A[i] == B[j])
{
// If previous element
// are not from B[]
if (prev != 1)
{
// Update prev
prev = 1;
// Update j
j++;
}
// If previous element is
// not from A[]
else
{
// Update prev
prev = 0;
// Update i
i++;
}
}
// If it is not possible to merge two
// sorted arrays with given conditions
else
{
// Update flag
flag = false;
break;
}
}
return flag;
}
// Driver Code
public static void Main()
{
int[] A = { 3, 5, 8 };
int[] B = { 2, 4, 6 };
int N = A.Length;
if (checkIfPossibleMerge(A, B, N))
{
Console.WriteLine("Yes");
}
else
{
Console.WriteLine("No");
}
}
}
// This code is contributed by akhilsaini
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to check if it is possible to merge
// the two given arrays with given conditions
function checkIfPossibleMerge(A, B, N)
{
// Stores index of
// the array A[]
let i = 0;
// Stores index of
// the array B[]
let j = 0;
// Check if the previous element are from
// the array A[] or from the array B[]
let prev = -1;
// Check if it is possible to merge the two
// given sorted arrays with given conditions
let flag = true;
// Traverse both the arrays
while (i < N && j < N)
{
// If A[i] is less than B[j] and
// previous element are not from A[]
if (A[i] < B[j] && prev != 0)
{
// Update prev
prev = 0;
// Update i
i++;
}
// If B[j] is less than A[i] and
// previous element are not from B[]
else if (B[j] < A[i] && prev != 1)
{
// Update prev
prev = 1;
// Update j
j++;
}
// If A[i] equal to B[j]
else if (A[i] == B[j])
{
// If previous element
// are not from B[]
if (prev != 1)
{
// Update prev
prev = 1;
// Update j
j++;
}
// If previous element is
// not from A[]
else
{
// Update prev
prev = 0;
// Update i
i++;
}
}
// If it is not possible to merge two
// sorted arrays with given conditions
else
{
// Update flag
flag = false;
break;
}
}
return flag;
}
// Driver Code
let A = [ 3, 5, 8 ];
let B = [ 2, 4, 6 ];
let N = A.length;
if (checkIfPossibleMerge(A, B, N))
{
document.write("Yes");
}
else
{
document.write("No");
}
// This code is contributed by splevel62.
</script>
Producción:
Yes
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por ManikantaBandla y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA