Dadas dos arrays que constan de N enteros distintos, de modo que la array A[] y B[] están ordenadas en orden ascendente y descendente respectivamente, la tarea es encontrar el número de valores comunes en ambas arrays.
Ejemplos:
Entrada: A[] = {1, 10, 100}, B[] = {200, 20, 2}
Salida: 0Entrada: A[] = {2, 4, 5, 8, 12, 13, 17, 18, 20, 22, 309, 999}, B[] = {109, 99, 68, 54, 22, 19, 17 , 13, 11, 5, 3, 1}
Salida: 4
Enfoque: El problema dado se puede resolver utilizando el enfoque de dos punteros . Siga los pasos a continuación para resolver el problema:
- Inicialice dos variables, digamos primero como 0 y segundo como (N – 1) que se usa para recorrer la array A[] y B[] desde el frente y atrás respectivamente.
- Inicialice una variable, digamos contar como 0 que almacena el recuento de números comunes en la array A[] y B[] .
- Iterar un ciclo hasta que primero < N y segundo >= 0 y realizar los siguientes pasos:
- Si el valor de A[primero] es igual a B[segundo] , entonces incremente los valores de contar y primero y disminuya el valor de segundo .
- Si el valor de A[primero] es menor que B[segundo] , incremente el valor de primero .
- Si el valor de A[primero] es mayor que B[segundo] , disminuya el valor del segundo .
- Después de completar los pasos anteriores, imprima el valor de conteo como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count the number of
// elements common in both the arrays
int countEqual(int A[], int B[], int N)
{
// Used to traverse array A[] and
// B[] from the front and the back
int first = 0;
int second = N - 1;
// Stores the count of numbers
// common in both array
int count = 0;
while (first < N && second >= 0) {
// If A[first] is less than
// B[second]
if (A[first] < B[second]) {
// Increment the value
// of first
first++;
}
// IF B[second] is less
// than A[first]
else if (B[second] < A[first]) {
// Decrement the value
// of second
second--;
}
// A[first] is equal to
// B[second]
else {
// Increment the value
// of count
count++;
// Increment the value
// of first
first++;
// Decrement the value
// of second
second--;
}
}
// Return the value of count
return count;
}
// Driver Code
int main()
{
int A[] = { 2, 4, 5, 8, 12, 13, 17,
18, 20, 22, 309, 999 };
int B[] = { 109, 99, 68, 54, 22, 19,
17, 13, 11, 5, 3, 1 };
int N = sizeof(A) / sizeof(int);
cout << countEqual(A, B, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG
{
// Function to count the number of
// elements common in both the arrays
static int countEqual(int A[], int B[], int N)
{
// Used to traverse array A[] and
// B[] from the front and the back
int first = 0;
int second = N - 1;
// Stores the count of numbers
// common in both array
int count = 0;
while (first < N && second >= 0) {
// If A[first] is less than
// B[second]
if (A[first] < B[second]) {
// Increment the value
// of first
first++;
}
// IF B[second] is less
// than A[first]
else if (B[second] < A[first]) {
// Decrement the value
// of second
second--;
}
// A[first] is equal to
// B[second]
else {
// Increment the value
// of count
count++;
// Increment the value
// of first
first++;
// Decrement the value
// of second
second--;
}
}
// Return the value of count
return count;
}
// Driver Code
public static void main(String[] args)
{
int A[] = { 2, 4, 5, 8, 12, 13, 17,
18, 20, 22, 309, 999 };
int B[] = { 109, 99, 68, 54, 22, 19,
17, 13, 11, 5, 3, 1 };
int N = A.length;
System.out.println(countEqual(A, B, N));
}
}
// This code is contributed by susmitakundugoaldanga.
Python3
# Python program for the above approach # Function to count the number of # elements common in both the arrays def countEqual(A, B, N) : # Used to traverse array A[] and # B[] from the front and the back first = 0 second = N - 1 # Stores the count of numbers # common in both array count = 0 while (first < N and second >= 0) : # If A[first] is less than # B[second] if (A[first] < B[second]) : # Increment the value # of first first += 1 # IF B[second] is less # than A[first] elif (B[second] < A[first]) : # Decrement the value # of second second -= 1 # A[first] is equal to # B[second] else : # Increment the value # of count count += 1 # Increment the value # of first first += 1 # Decrement the value # of second second -= 1 # Return the value of count return count # Driver Code A= [ 2, 4, 5, 8, 12, 13, 17, 18, 20, 22, 309, 999 ] B = [ 109, 99, 68, 54, 22, 19, 17, 13, 11, 5, 3, 1 ] N = len(A) print(countEqual(A, B, N)) # This code is contributed by sanjou_62.
C#
// C# program for the above approach
using System;
class GFG{
// Function to count the number of
// elements common in both the arrays
static int countEqual(int[] A, int[] B, int N)
{
// Used to traverse array A[] and
// B[] from the front and the back
int first = 0;
int second = N - 1;
// Stores the count of numbers
// common in both array
int count = 0;
while (first < N && second >= 0)
{
// If A[first] is less than
// B[second]
if (A[first] < B[second])
{
// Increment the value
// of first
first++;
}
// IF B[second] is less
// than A[first]
else if (B[second] < A[first])
{
// Decrement the value
// of second
second--;
}
// A[first] is equal to
// B[second]
else
{
// Increment the value
// of count
count++;
// Increment the value
// of first
first++;
// Decrement the value
// of second
second--;
}
}
// Return the value of count
return count;
}
// Driver code
static void Main()
{
int[] A = { 2, 4, 5, 8, 12, 13,
17, 18, 20, 22, 309, 999 };
int[] B = { 109, 99, 68, 54, 22, 19,
17, 13, 11, 5, 3, 1 };
int N = A.Length;
Console.WriteLine(countEqual(A, B, N));
}
}
// This code is contributed by abhinavjain194
Javascript
<script>
// Javascript program for the above approach
// Function to count the number of
// elements common in both the arrays
function countEqual(A, B, N)
{
// Used to traverse array A[] and
// B[] from the front and the back
let first = 0;
let second = N - 1;
// Stores the count of numbers
// common in both array
let count = 0;
while (first < N && second >= 0) {
// If A[first] is less than
// B[second]
if (A[first] < B[second]) {
// Increment the value
// of first
first++;
}
// IF B[second] is less
// than A[first]
else if (B[second] < A[first]) {
// Decrement the value
// of second
second--;
}
// A[first] is equal to
// B[second]
else {
// Increment the value
// of count
count++;
// Increment the value
// of first
first++;
// Decrement the value
// of second
second--;
}
}
// Return the value of count
return count;
}
// Driver Code
let A = [2, 4, 5, 8, 12, 13, 17,
18, 20, 22, 309, 999];
let B = [109, 99, 68, 54, 22, 19,
17, 13, 11, 5, 3, 1];
let N = A.length;
document.write(countEqual(A, B, N));
// This code is contributed _saurabh_jaiswal
</script>
Producción:
4
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por nichil942singh y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA