Dadas dos arrays a[] y b[] de longitud N y M respectivamente, ordenadas en orden no decreciente . La tarea es encontrar el número de pares (i, j) tales que a[i] es igual a b[j] .
Ejemplos:
Entrada: a[] = {1, 1, 3, 3, 3, 5, 8, 8}, b[] = {1, 3, 3, 4, 5, 5, 5}
Salida: 11
Explicación: Los siguientes son los 11 pares con la condición dada Los 11 pares son {{1, 1}, {1, 1}, {3, 3}, {3, 3}, {3, 3}, {3, 3}, {3, 3}, {3, 3}, {5, 5}, {5, 5}, {5, 5}} .Entrada: a[] = {1, 2, 3, 4}, b[] = {1, 1, 2}
Salida: 3
Enfoque: este problema se puede resolver utilizando el enfoque de dos punteros . Deje que i apunte al primer elemento de la array a[] y j apunte al primer elemento de la array b[] . Al atravesar las arrays , habrá 3 casos.
Caso 1: a[i] = b[j] Deje que target denote arr[i], cnt1 denote la cantidad de elementos de la array a que son iguales a target y cnt2 denote la cantidad de elementos de la array b que son iguales a target. Entonces, el número total de pares tales que a[i] = b[j] es cnt1 * cnt2 . Entonces nuestra respuesta se incrementa en cnt1 * cnt2 .
Caso 2: a[i] < b[j] La única posibilidad de obtener a[i] = b[j] en el futuro es incrementando i, entonces hacemos i++.
Caso 3: a[i] > b[j] La única posibilidad de obtener a[i] = b[j] en el futuro es incrementando j, entonces hacemos j++ .
Siga los pasos a continuación para resolver el problema dado.
- Inicialice las variables ans, i y j como 0.
- Inicialice answer, i , y j a 0 y comience a recorrer ambos arreglos hasta que i sea menor que N o j sea menor que M .
- Si a[i] es igual a b[j], calcule cnt1 y cnt2 e incremente la respuesta en cnt1 * cnt2 .
- Si a[i] es menor que b[j], incremente i .
- Si a[i] es mayor que b[j], incremente j .
- Después de realizar los pasos anteriores, imprima los valores de ans como respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program for above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find number of pairs with
// satisfying the given condition
int findPairs(int* a, int* b, int n, int m)
{
// Initialize ans, i, j to 0 .
int ans = 0, i = 0, j = 0;
// Use the two pointer approach to
// calculate the answer .
while (i < n && j < m) {
// Case - 1
if (a[i] == b[j]) {
// Target denotes a[i]
// or b[j] as a[i] = b[j].
// cnt1 denotes the number
// of elements in array
// a that are equal to target.
// cnt2 denotes the number
// of elements in array
// b that are equal to target
int target = a[i], cnt1 = 0, cnt2 = 0;
// Calculate cnt1
while (i < n && a[i] == target) {
cnt1++;
i++;
}
// Calculate cnt2
while (j < m && b[j] == target) {
cnt2++;
j++;
}
// Increment the answer by (cnt1 * cnt2)
ans += (cnt1 * cnt2);
}
// Case - 2
else if (a[i] < b[j])
i++;
// Case - 3
else
j++;
}
// Return the answer
return ans;
}
// Driver Code
int main()
{
int N = 8, M = 7;
int a[] = { 1, 1, 3, 3, 3, 5, 8, 8 };
int b[] = { 1, 3, 3, 4, 5, 5, 5 };
cout << findPairs(a, b, N, M);
}
Java
// Java program for above approach
import java.io.*;
class GFG{
// Function to find number of pairs with
// satisfying the given condition
static int findPairs(int[] a, int[] b, int n, int m)
{
// Initialize ans, i, j to 0 .
int ans = 0, i = 0, j = 0;
// Use the two pointer approach to
// calculate the answer .
while (i < n && j < m)
{
// Case - 1
if (a[i] == b[j])
{
// Target denotes a[i]
// or b[j] as a[i] = b[j].
// cnt1 denotes the number
// of elements in array
// a that are equal to target.
// cnt2 denotes the number
// of elements in array
// b that are equal to target
int target = a[i], cnt1 = 0, cnt2 = 0;
// Calculate cnt1
while (i < n && a[i] == target)
{
cnt1++;
i++;
}
// Calculate cnt2
while (j < m && b[j] == target)
{
cnt2++;
j++;
}
// Increment the answer by (cnt1 * cnt2)
ans += (cnt1 * cnt2);
}
// Case - 2
else if (a[i] < b[j])
i++;
// Case - 3
else
j++;
}
// Return the answer
return ans;
}
// Driver Code
public static void main(String[] args)
{
int N = 8, M = 7;
int a[] = { 1, 1, 3, 3, 3, 5, 8, 8 };
int b[] = { 1, 3, 3, 4, 5, 5, 5 };
System.out.println(findPairs(a, b, N, M));
}
}
// This code is contributed by Potta Lokesh
Python3
# Python3 program for above approach # Function to find number of pairs with # satisfying the given condition def findPairs(a, b, n, m): # Initialize ans, i, j to 0 . ans = 0 i = 0 j = 0 # Use the two pointer approach to # calculate the answer . while (i < n and j < m): # Case - 1 if (a[i] == b[j]): # Target denotes a[i] # or b[j] as a[i] = b[j]. # cnt1 denotes the number # of elements in array # a that are equal to target. # cnt2 denotes the number # of elements in array # b that are equal to target target = a[i] cnt1 = 0 cnt2 = 0 # Calculate cnt1 while (i < n and a[i] == target): cnt1 += 1 i += 1 # Calculate cnt2 while (j < m and b[j] == target): cnt2 += 1 j += 1 # Increment the answer by (cnt1 * cnt2) ans += (cnt1 * cnt2) # Case - 2 elif (a[i] < b[j]): i += 1 # Case- 3 else: j += 1 # Return the answer return ans # Driver Code if __name__ == "__main__": N = 8 M = 7 a = [ 1, 1, 3, 3, 3, 5, 8, 8 ] b = [ 1, 3, 3, 4, 5, 5, 5 ] print(findPairs(a, b, N, M)) # This code is contributed by ukasp
C#
// C# program for above approach
using System;
class GFG{
// Function to find number of pairs with
// satisfying the given condition
static int findPairs(int[] a, int[] b, int n, int m)
{
// Initialize ans, i, j to 0 .
int ans = 0, i = 0, j = 0;
// Use the two pointer approach to
// calculate the answer .
while (i < n && j < m)
{
// Case - 1
if (a[i] == b[j])
{
// Target denotes a[i]
// or b[j] as a[i] = b[j].
// cnt1 denotes the number
// of elements in array
// a that are equal to target.
// cnt2 denotes the number
// of elements in array
// b that are equal to target
int target = a[i], cnt1 = 0, cnt2 = 0;
// Calculate cnt1
while (i < n && a[i] == target)
{
cnt1++;
i++;
}
// Calculate cnt2
while (j < m && b[j] == target)
{
cnt2++;
j++;
}
// Increment the answer by (cnt1 * cnt2)
ans += (cnt1 * cnt2);
}
// Case - 2
else if (a[i] < b[j])
i++;
// Case - 3
else
j++;
}
// Return the answer
return ans;
}
// Driver Code
public static void Main()
{
int N = 8, M = 7;
int []a = { 1, 1, 3, 3, 3, 5, 8, 8 };
int []b = { 1, 3, 3, 4, 5, 5, 5 };
Console.Write(findPairs(a, b, N, M));
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// Javascript Program for above approach
// Function to find number of pairs with
// satisfying the given condition
function findPairs(a, b, n, m)
{
// Initialize ans, i, j to 0 .
let ans = 0, i = 0, j = 0;
// Use the two pointer approach to
// calculate the answer .
while (i < n && j < m) {
// Case - 1
if (a[i] == b[j]) {
// Target denotes a[i]
// or b[j] as a[i] = b[j].
// cnt1 denotes the number
// of elements in array
// a that are equal to target.
// cnt2 denotes the number
// of elements in array
// b that are equal to target
let target = a[i], cnt1 = 0, cnt2 = 0;
// Calculate cnt1
while (i < n && a[i] == target) {
cnt1++;
i++;
}
// Calculate cnt2
while (j < m && b[j] == target) {
cnt2++;
j++;
}
// Increment the answer by (cnt1 * cnt2)
ans += (cnt1 * cnt2);
}
// Case - 2
else if (a[i] < b[j])
i++;
// Case - 3
else
j++;
}
// Return the answer
return ans;
}
// Driver Code
let N = 8, M = 7;
let a = [ 1, 1, 3, 3, 3, 5, 8, 8 ];
let b = [ 1, 3, 3, 4, 5, 5, 5 ];
document.write(findPairs(a, b, N, M));
// This code is contributed by saurabh_jaiswal.
</script>
11
Complejidad temporal: O(N + M)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por nikhilkumarmishra120 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA