原文:
给定一个 n 个整数的数组，你必须找到选择随机对(i，j)的概率，i < j such that a[i] a[j] is maximum. 例:
input : a[] = {3, 3, 3, 3}
output : 1.0000
explanation :
here, maximum sum we can get by selecting
any pair is 6.
total number of pairs possible = 6.
pairs with maximum sum = 6.
probability = 6/6 = 1.0000
input : a[] = {1, 2, 2, 3}
output : 0.3333
explanation :
here, maximum sum we can get by selecting
a pair is 5.
total number of pairs possible = 6.
pairs with maximum sum = {2, 3} and {2, 3} = 2.
probability = 2/6 = 0.3333
probability(event) = number of favorable outcomes /
total number of outcomes
天真的方法:我们可以使用蛮力解整体对(i，j)来解决这个问题，i < j 获得可能的最大值，然后再次执行蛮力来计算达到最大值的次数。 有效方法:注意，只有当对由数组的第一个和第二个最大元素组成时，我们才能得到最大对和。因此，问题是计算这些元素出现的次数，并使用公式计算有利的结果。
favorable outcomes = f2 (frequency of second maximum
element(f2), if maximum element occurs only once).
or
favorable outcomes = f1 * (f1 - 1) / 2,
(when frequency of maximum element(f1)
is greater than 1).
c
// cpp program of choosing a random pair
// such that a[i] a[j] is maximum.
#include
using namespace std;
// function to get max first and second
int countmaxsumpairs(int a[], int n)
{
int first = int_min, second = int_min;
for (int i = 0; i < n; i ) {
/* if current element is smaller than
first, then update both first and
second */
if (a[i] > first) {
second = first;
first = a[i];
}
/* if arr[i] is in between first and
second then update second */
else if (a[i] > second && a[i] != first)
second = a[i];
}
int cnt1 = 0, cnt2 = 0;
for (int i = 0; i < n; i ) {
if (a[i] == first)
cnt1 ; // frequency of first maximum
if (a[i] == second)
cnt2 ; // frequency of second maximum
}
if (cnt1 == 1)
return cnt2;
if (cnt1 > 1)
return cnt1 * (cnt1 - 1) / 2;
}
// returns probability of choosing a pair with
// maximum sum.
float findmaxsumprobability(int a[], int n)
{
int total = n * (n - 1) / 2;
int max_sum_pairs = countmaxsumpairs(a, n);
return (float)max_sum_pairs/(float)total;
}
// driver code
int main()
{
int a[] = { 1, 2, 2, 3 };
int n = sizeof(a) / sizeof(a[0]);
cout << findmaxsumprobability(a, n);
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// java program of choosing a random pair
// such that a[i] a[j] is maximum.
import java.util.scanner;
import java.io.*;
class gfg {
// function to get max first and second
static int countmaxsumpairs(int a[], int n)
{
int first = integer.min_value, second = integer.min_value;
for (int i = 0; i < n; i ) {
/* if current element is smaller than
first, then update both first and
second */
if (a[i] > first)
{
second = first;
first = a[i];
}
/* if arr[i] is in between first and
second then update second */
else if (a[i] > second && a[i] != first)
second = a[i];
}
int cnt1 = 0, cnt2 = 0;
for (int i = 0; i < n; i ) {
if (a[i] == first)
// frequency of first maximum
cnt1 ;
if (a[i] == second)
// frequency of second maximum
cnt2 ;
}
if (cnt1 == 1)
return cnt2;
if (cnt1 > 1)
return cnt1 * (cnt1 - 1) / 2;
return 0;
}
// returns probability of choosing a pair with
// maximum sum.
static float findmaxsumprobability(int a[], int n)
{
int total = n * (n - 1) / 2;
int max_sum_pairs = countmaxsumpairs(a, n);
return (float)max_sum_pairs/(float)total;
}
// driver code
public static void main (string[] args) {
int a[] = { 1, 2, 2, 3 };
int n = a.length;;
system.out.println(findmaxsumprobability(a, n));
// this code is contributed by ajit
}
}
python 3
# python 3 program of choosing a random
# pair such that a[i] a[j] is maximum.
# function to get max first and second
def countmaxsumpairs(a, n):
first = 0
second = 0
for i in range(n):
# if current element is smaller than
# first, then update both first and
# second
if (a[i] > first) :
second = first
first = a[i]
# if arr[i] is in between first and
# second then update second
elif (a[i] > second and a[i] != first):
second = a[i]
cnt1 = 0
cnt2 = 0
for i in range(n):
if (a[i] == first):
cnt1 = 1 # frequency of first maximum
if (a[i] == second):
cnt2 = 1 # frequency of second maximum
if (cnt1 == 1) :
return cnt2
if (cnt1 > 1) :
return cnt1 * (cnt1 - 1) / 2
# returns probability of choosing a pair
# with maximum sum.
def findmaxsumprobability(a, n):
total = n * (n - 1) / 2
max_sum_pairs = countmaxsumpairs(a, n)
return max_sum_pairs / total
# driver code
if __name__ == "__main__":
a = [ 1, 2, 2, 3 ]
n = len(a)
print(findmaxsumprobability(a, n))
# this code is contributed by ita_c
c
// c# program of choosing a random pair
// such that a[i] a[j] is maximum.
using system;
public class gfg{
// function to get max first and second
static int countmaxsumpairs(int []a, int n)
{
int first = int.minvalue, second = int.minvalue;
for (int i = 0; i < n; i ) {
/* if current element is smaller than
first, then update both first and
second */
if (a[i] > first)
{
second = first;
first = a[i];
}
/* if arr[i] is in between first and
second then update second */
else if (a[i] > second && a[i] != first)
second = a[i];
}
int cnt1 = 0, cnt2 = 0;
for (int i = 0; i < n; i ) {
if (a[i] == first)
// frequency of first maximum
cnt1 ;
if (a[i] == second)
// frequency of second maximum
cnt2 ;
}
if (cnt1 == 1)
return cnt2;
if (cnt1 > 1)
return cnt1 * (cnt1 - 1) / 2;
return 0;
}
// returns probability of choosing a pair with
// maximum sum.
static float findmaxsumprobability(int []a, int n)
{
int total = n * (n - 1) / 2;
int max_sum_pairs = countmaxsumpairs(a, n);
return (float)max_sum_pairs/(float)total;
}
// driver code
static public void main ()
{
int []a = { 1, 2, 2, 3 };
int n = a.length;;
console.writeline(findmaxsumprobability(a, n));
}
}
// this code is contributed by vt_m.
服务器端编程语言（professional hypertext preprocessor 的缩写）
$first)
{
$second = $first;
$first = $a[$i];
}
// if arr[i] is in between
// first and second then
// update second
else if ($a[$i] > $second &&
$a[$i] != $first)
$second = $a[$i];
}
$cnt1 = 0;
$cnt2 = 0;
for ($i = 0; $i < $n; $i )
{
if ($a[$i] == $first)
// frequency of first maximum
$cnt1 ;
if ($a[$i] == $second)
// frequency of second maximum
$cnt2 ;
}
if ($cnt1 == 1)
return $cnt2;
if ($cnt1 > 1)
return $cnt1 * ($cnt1 - 1) / 2;
}
// returns probability of
// choosing a pair with
// maximum sum.
function findmaxsumprobability($a, $n)
{
$total = $n * ($n - 1) / 2;
$max_sum_pairs = countmaxsumpairs($a, $n);
return (float)$max_sum_pairs / (float) $total;
}
// driver code
$a= array (1, 2, 2, 3 );
$n = sizeof($a);
echo findmaxsumprobability($a, $n);
// this code is contributed by ajit
?>
java 描述语言
输出:
0.333333
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
