# 計算選擇差異最大的對的方法 > 原文： [https://www.geeksforgeeks.org/count-ways-of-choosing-a-pair-with-maximum-difference/](https://www.geeksforgeeks.org/count-ways-of-choosing-a-pair-with-maximum-difference/) 給定 n 個整數數組，我們需要找到 no。 選擇差異最大的對的方式。 例子： ``` 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)` **有效方法**： 有效方法是： * 情況一（如果所有元素都相等）：ans 否。 從一組 n（n-1）/ 2 個 n 元素中選擇 2 個元素的方法。 * 情況二（如果所有要素都不相等）：答案是否的計數的乘積。 最小元素（c1）的數量和數量 最大元素（c2）的總和，即 c1 * c2 ## C++ ```cpp // 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 // 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 ```py # 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# ```cs // 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 // 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)`