Dadas dos arrays A y B, se elige un par aleatorio que tiene un elemento de la array A y otro de la array B. Muestra la probabilidad de que el par tenga la máxima ponderación.
Ejemplos:
Input : A[] = 1 2 3
B[] = 1 3 3
Output : 0.222
Explanation : Possible pairs are : {1, 1},
{1, 3}, {1, 3}, {2, 1}, {2, 3}, {2, 3},
{3, 1}, {3, 3}, {3, 3} i.e. 9.
The pair with maximum weight is {3, 3} with
frequency 2. So, the probability of random
pair being maximum is 2/9 = 0.2222.
- Método de fuerza bruta: genere todos los pares posibles en N^2 complejidad de tiempo y cuente
los pares ponderados máximos. - Mejor método: ordene ambas arrays y cuente los últimos elementos (máx.) de A y B. El número máximo de pares ponderados será el producto de ambos conteos. La probabilidad será
(producto de conteos) / tamaño de (A) * tamaño de (B) - Mejor método El mejor enfoque será atravesar ambas arrays y contar el elemento máximo. El número máximo de pares ponderados será el producto de ambos cómputos. La probabilidad será (producto de conteos) / tamaño de (A) * tamaño de (B)
A continuación se muestra la implementación:
C++
#include <bits/stdc++.h>
using namespace std;
// Function to return probability
double probability(int a[], int b[], int size1,
int size2)
{
// Count occurrences of maximum element
// in A[]
int max1 = INT_MIN, count1 = 0;
for (int i = 0; i < size1; i++) {
if (a[i] > max1) {
max1 = a[i];
count1 = 1;
}
else if (a[i] == max1) {
count1++;
}
}
// Count occurrences of maximum element
// in B[]
int max2 = INT_MIN, count2 = 0;
for (int i = 0; i < size2; i++) {
if (b[i] > max2) {
max2 = b[i];
count2 = 1;
}
else if (b[i] == max2) {
count2++;
}
}
// Returning probability
return (double)(count1 * count2) /
(size1 * size2);
}
// Driver code
int main()
{
int a[] = { 1, 2, 3 };
int b[] = { 1, 3, 3 };
int size1 = sizeof(a) / sizeof(a[0]);
int size2 = sizeof(b) / sizeof(b[0]);
cout << probability(a, b, size1, size2);
return 0;
}
Java
// Java program to find Probability
// of a random pair being the maximum
// weighted pair
import java.io.*;
class GFG {
// Function to return probability
static double probability(int a[], int b[],
int size1,int size2)
{
// Count occurrences of maximum
// element in A[]
int max1 = Integer.MIN_VALUE, count1 = 0;
for (int i = 0; i < size1; i++) {
if (a[i] > max1) {
max1 = a[i];
count1 = 1;
}
else if (a[i] == max1) {
count1++;
}
}
// Count occurrences of maximum
// element in B[]
int max2 = Integer.MIN_VALUE, count2 = 0;
for (int i = 0; i < size2; i++) {
if (b[i] > max2) {
max2 = b[i];
count2 = 1;
}
else if (b[i] == max2) {
count2++;
}
}
// Returning probability
return (double)(count1 * count2) / (size1 * size2);
}
// Driver code
public static void main(String args[])
{
int a[] = { 1, 2, 3 };
int b[] = { 1, 3, 3 };
int size1 = a.length;
int size2 = b.length;
System.out.println(probability(a, b,
size1, size2));
}
}
/*This code is contributed by Nikita Tiwari.*/
Python3
import sys # Function to return probability def probability(a, b, size1, size2): # Count occurrences of maximum # element in A[] max1 = -(sys.maxsize - 1) count1 = 0 for i in range(size1): if a[i] > max1: count1 = 1 elif a[i] == max1: count1 += 1 # Count occurrences of maximum # element in B[] max2 = -(sys.maxsize - 1) count2 = 0 for i in range(size2): if b[i] > max2: max2 = b[i] count2 = 1 elif b[i] == max2: count2 += 1 # Returning probability return round((count1 * count2) / (size1 * size2), 6) # Driver code a = [1, 2, 3] b = [1, 3, 3] size1 = len(a) size2 = len(b) print(probability(a, b, size1, size2)) # This code is contributed # by Shrikant13
C#
// C# program to find Probability of a random
// pair being the maximum weighted pair
using System;
class GFG {
// Function to return probability
static float probability(int []a, int []b,
int size1,int size2)
{
// Count occurrences of maximum
// element in A[]
int max1 = int.MinValue, count1 = 0;
for (int i = 0; i < size1; i++) {
if (a[i] > max1) {
max1 = a[i];
count1 = 1;
}
else if (a[i] == max1) {
count1++;
}
}
// Count occurrences of maximum
// element in B[]
int max2 = int.MinValue, count2 = 0;
for (int i = 0; i < size2; i++) {
if (b[i] > max2) {
max2 = b[i];
count2 = 1;
}
else if (b[i] == max2) {
count2++;
}
}
// Returning probability
return (float)(count1 * count2) /
(size1 * size2);
}
// Driver code
public static void Main()
{
int []a = { 1, 2, 3 };
int []b = { 1, 3, 3 };
int size1 = a.Length;
int size2 = b.Length;
Console.WriteLine(probability(a, b,
size1, size2));
}
}
/* This code is contributed by vt_m.*/
PHP
<?php
// PHP program for Probability of
// a random pair being the maximum
// weighted pair
// Function to return probability
function probability($a, $b,
$size1, $size2)
{
// Count occurrences of maximum
// element in A[]
$max1 = PHP_INT_MIN; $count1 = 0;
for ($i = 0; $i < $size1; $i++)
{
if ($a[$i] > $max1)
{
$max1 = $a[$i];
$count1 = 1;
}
else if ($a[$i] == $max1)
{
$count1++;
}
}
// Count occurrences of maximum
// element in B[]
$max2 = PHP_INT_MIN; $count2 = 0;
for ($i = 0; $i < $size2; $i++)
{
if ($b[$i] > $max2)
{
$max2 = $b[$i];
$count2 = 1;
}
else if ($b[$i] == $max2)
{
$count2++;
}
}
// Returning probability
return (double)($count1 * $count2) /
($size1 * $size2);
}
// Driver code
$a = array(1, 2, 3);
$b = array(1, 3, 3);
$size1 = sizeof($a);
$size2 = sizeof($b);
echo probability($a, $b,
$size1, $size2);
// This code is contributed by ajit
?>
Javascript
<script>
// JavaScript program to find Probability
// of a random pair being the maximum
// weighted pair
// Function to return probability
function probability(a, b, size1, size2)
{
// Count occurrences of maximum
// element in A[]
let max1 = Number.MIN_VALUE, count1 = 0;
for(let i = 0; i < size1; i++)
{
if (a[i] > max1)
{
max1 = a[i];
count1 = 1;
}
else if (a[i] == max1)
{
count1++;
}
}
// Count occurrences of maximum
// element in B[]
let max2 = Number.MIN_VALUE, count2 = 0;
for(let i = 0; i < size2; i++)
{
if (b[i] > max2)
{
max2 = b[i];
count2 = 1;
}
else if (b[i] == max2)
{
count2++;
}
}
// Returning probability
return (count1 * count2) /
(size1 * size2);
}
// Driver Code
let a = [ 1, 2, 3 ];
let b = [ 1, 3, 3 ];
let size1 = a.length;
let size2 = b.length;
document.write(probability(a, b,
size1, size2));
// This code is contributed by code_hunt
</script>
Producción
0.222222
Complejidad temporal: O(n).
Espacio Auxiliar: O(1).
Publicación traducida automáticamente
Artículo escrito por Rohit Thapliyal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA