计算选择差异最大的偶对的方法数量
原文： https://www.geeksforgeeks.org/count-ways-of-choosing-a-pair-with-maximum-difference/
给定n个整数数组，我们需要找到选择差异最大的对的方式数量。
例子：
Input : a[] = {3, 2, 1, 1, 3}
Output : 4
Explanation:- Here, the maximum difference
you can find is 2 which is from (1, 3).
No. of ways of choosing it:
1) Choosing the first and third elements,
2) Choosing the first and fourth elements,
3) Choosing the third and fifth elements,
4) Choosing the fourth and fifth elements.
Hence ans is 4.
Input : a[] = {2, 4, 1, 1}
Output : 2
Explanation:- Here, the maximum difference
is 3 from (1, 4). No. of ways choosing it:
1) Choosing the second and third elements,
2) Choosing the second and fourth elements.
Hence ans is 2.
朴素的方法：一个简单的解决方案是找到最小元素和最大元素以找到最大差异。 然后我们可以找到否。 通过运行两个循环选择一对的方法。 在内部循环中，检查两个元素（一个在外部循环中，另一个在内部循环中）是否有最大差异，如果是，则增加计数。最后输出计数。
时间复杂度：O(n ^ 2)。
辅助空间：O(1)。
有效方法：
-
情况一（如果所有元素都相等）：答案是从一组
n个元素中选择 2 个元素的方法数量，C(n, 2) = n(n-1) / 2。 -
情况二（如果所有要素都不相等）：答案是最小元素（
c1）的数量和最大元素（c2）数量的乘积，即c1 * c2。
C++
// CPP Code to find no. of Ways of choosing
// a pair with maximum difference
#include <bits/stdc++.h>
using namespace std;
int countPairs(int a[], int n)
{
// To find minimum and maximum of
// the array
int mn = INT_MAX;
int mx = INT_MIN;
for (int i = 0; i < n; i++) {
mn = min(mn, a[i]);
mx = max(mx, a[i]);
}
// to find the count of minimum and
// maximum elements
int c1 = 0;
int c2 = 0; // Count variables
for (int i = 0; i < n; i++) {
if (a[i] == mn)
c1++;
if (a[i] == mx)
c2++;
}
// condition for all elements equal
if (mn == mx)
return n * (n - 1) / 2;
else
return c1 * c2;
}
// Driver code
int main()
{
int a[] = { 3, 2, 1, 1, 3 };
int n = sizeof(a) / sizeof(a[0]);
cout << countPairs(a, n);
return 0;
}
Java
// Java Code to find no. of Ways of choosing
// a pair with maximum difference
import java.util.*;
class GFG {
static int countPairs(int a[], int n)
{
// To find minimum and maximum of
// the array
int mn = Integer.MAX_VALUE;
int mx = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
mn = Math.min(mn, a[i]);
mx = Math.max(mx, a[i]);
}
// to find the count of minimum and
// maximum elements
int c1 = 0;
int c2 = 0; // Count variables
for (int i = 0; i < n; i++) {
if (a[i] == mn)
c1++;
if (a[i] == mx)
c2++;
}
// condition for all elements equal
if (mn == mx)
return n * (n - 1) / 2;
else
return c1 * c2;
}
// Driver code
public static void main(String[] args)
{
int a[] = { 3, 2, 1, 1, 3 };
int n = a.length;
System.out.print(countPairs(a, n));
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python Code to find no.
# of Ways of choosing
# a pair with maximum difference
def countPairs(a, n):
# To find minimum and maximum of
# the array
mn = +2147483647
mx = -2147483648
for i in range(n):
mn = min(mn, a[i])
mx = max(mx, a[i])
# to find the count of minimum and
# maximum elements
c1 = 0
c2 = 0 # Count variables
for i in range(n):
if (a[i] == mn):
c1+= 1
if (a[i] == mx):
c2+= 1
# condition for all elements equal
if (mn == mx):
return n*(n - 1) // 2
else:
return c1 * c2
# Driver code
a = [ 3, 2, 1, 1, 3]
n = len(a)
print(countPairs(a, n))
# This code is contributed
# by Anant Agarwal.
C#
// C# Code to find no. of Ways of choosing
// a pair with maximum difference
using System;
class GFG {
static int countPairs(int[] a, int n)
{
// To find minimum and maximum of
// the array
int mn = int.MaxValue;
int mx = int.MinValue;
for (int i = 0; i < n; i++) {
mn = Math.Min(mn, a[i]);
mx = Math.Max(mx, a[i]);
}
// to find the count of minimum and
// maximum elements
int c1 = 0;
int c2 = 0; // Count variables
for (int i = 0; i < n; i++) {
if (a[i] == mn)
c1++;
if (a[i] == mx)
c2++;
}
// condition for all elements equal
if (mn == mx)
return n * (n - 1) / 2;
else
return c1 * c2;
}
// Driver code
public static void Main()
{
int[] a = { 3, 2, 1, 1, 3 };
int n = a.Length;
Console.WriteLine(countPairs(a, n));
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP Code to find no. of Ways of choosing
// a pair with maximum difference
function countPairs($a, $n)
{
// To find minimum and maximum of
// the array
$mn = PHP_INT_MAX;
$mx = PHP_INT_MIN;
for ($i = 0; $i < $n; $i++) {
$mn = min($mn, $a[$i]);
$mx = max($mx, $a[$i]);
}
// to find the count of minimum and
// maximum elements
$c1 = 0;
$c2 = 0; // Count variables
for ($i = 0; $i < $n; $i++) {
if ($a[$i] == $mn)
$c1++;
if ($a[$i] == $mx)
$c2++;
}
// condition for all elements equal
if ($mn == $mx)
return $n * ($n - 1) / 2;
else
return $c1 * $c2;
}
// Driver code
$a = array( 3, 2, 1, 1, 3 );
$n = count($a);
echo countPairs($a, $n);
// This code is contributed by anuj_67\.
?>
Output:
4
时间复杂度：找到最小和最大值的时间复杂度为O(n)，找到最小和最大计数的时间复杂度为O(n)。
总时间复杂度：O(n)。
辅助空间：O(1)。
版权属于：月萌API www.moonapi.com，转载请注明出处
