計算形成最小產品三胞胎的方法 · GeeksForGeeks 中文系列教程

# 計算形成最小產品三胞胎的方法 > 原文： [https://www.geeksforgeeks.org/count-ways-form-minimum-product-triplets/](https://www.geeksforgeeks.org/count-ways-form-minimum-product-triplets/) 給定一個正整數數組。我們需要找出索引（i，j，k）（i < j < k）的三倍數，以使 a [i] * a [j] * a [k]最小。 ``` Examples: Input : 5 1 3 2 3 4 Output : 2 The triplets are (1, 3, 2) and (1, 2, 3) Input : 5 2 2 2 2 2 Output : 5 In this example we choose three 2s out of five, and the number of ways to choose them is 5C3. Input : 6 1 3 3 1 3 2 Output : 1 There is only one way (1, 1, 2). ``` 在此問題中出現以下情況。 1. 所有三個最小元素都相同。例如{1，1，1，1，2，2，3，4}。對于這種情況的解決方案是 n C 3 。 2. 兩個元素是相同的。例如{1、2、2、2、3}或{1、1、2、2}。在這種情況下，第一個（或最小元素）的出現次數不能超過 2。如果最小元素出現兩次，則答案是第二個元素的計數（我們從第二個元素的所有出現中僅選擇 1 個。如果最小值元素出現一次，計數為 n C 2 。 3. 這三個要素都是截然不同的。例如{1、2、3、3、5}。在這種情況下，答案是第三元素（或 n C 1 ）的出現次數。我們首先按升序對數組進行排序。然后從開始計算第 3 元素的 3 元素的頻率。假設頻率為“計數”。出現以下情況。 * 如果第三個元素等于第一個元素，則否。三元組的數量為（count-2）*（count-1）*（count）/ 6，其中 count 是第 3 個元素的頻率。 * 如果第三個元素等于第二個元素，則否。三元組將為（count-1）*（count）/ 2。否則沒有。三元組將是計數值。 ## C++ ```cpp // CPP program to count number of ways we can // form triplets with minimum product. #include <bits/stdc++.h> using namespace std; // function to calculate number of triples long long noOfTriples(long long arr[], int n) { ????// Sort the array ????sort(arr, arr + n); ????// Count occurrences of third element ????long long count = 0; ????for (long long i = 0; i < n; i++)? ????????if (arr[i] == arr[2]) ????????????count++; ????// If all three elements are same (minimum ????// element appears at least 3 times). Answer ????// is nC3\. ????if (arr[0] == arr[2]) ????????return (count - 2) * (count - 1) * (count) / 6; ????// If minimum element appears once.?? ????// Answer is nC2\. ????else if (arr[1] == arr[2]) ????????return (count - 1) * (count) / 2; ????// Minimum two elements are distinct. ????// Answer is nC1\. ????return count; } // Driver code int main() { ????long long arr[] = { 1, 3, 3, 4 }; ????int n = sizeof(arr) / sizeof(arr[0]); ????cout << noOfTriples(arr, n); ????return 0; } ``` ## Java ```java // Java program to count number of ways we can // form triplets with minimum product. import java.util.Arrays; class GFG { ????// function to calculate number of triples ????static long noOfTriples(long arr[], int n) ????{ ????????// Sort the array ????????Arrays.sort(arr); ????????// Count occurrences of third element ????????long count = 0; ????????for (int i = 0; i < n; i++)? ????????????if (arr[i] == arr[2]) ????????????????count++; ????????// If all three elements are same (minimum ????????// element appears at least 3 times). Answer ????????// is nC3\. ????????if (arr[0] == arr[2]) ????????????return (count - 2) * (count - 1) *? ??????????????????????????????????????(count) / 6; ????????// If minimum element appears once.? ????????// Answer is nC2\. ????????else if (arr[1] == arr[2]) ????????????return (count - 1) * (count) / 2; ????????// Minimum two elements are distinct. ????????// Answer is nC1\. ????????return count; ????} ????//driver code ????public static void main(String arg[]) ????{ ????????long arr[] = { 1, 3, 3, 4 }; ????????int n = arr.length; ????????System.out.print(noOfTriples(arr, n)); ????} } // This code is contributed by Anant Agarwal. ``` ## Python3 ```py # Python3 program to count number # of ways we can form triplets? # with minimum product. # function to calculate number of triples def noOfTriples (arr, n): ????# Sort the array ????arr.sort() ????# Count occurrences of third element ????count = 0 ????for i in range(n): ????????if arr[i] == arr[2]: ????????????count+=1 ????# If all three elements are same? ????# (minimum element appears at l ????# east 3 times). Answer is nC3\. ????if arr[0] == arr[2]: ????????return (count - 2) * (count - 1) * (count) / 6 ????# If minimum element appears once. ????# Answer is nC2\. ????elif arr[1] == arr[2]: ????????return (count - 1) * (count) / 2 ????# Minimum two elements are distinct. ????# Answer is nC1\. ????return count # Driver code arr = [1, 3, 3, 4] n = len(arr) print (noOfTriples(arr, n)) # This code is contributed by "Abhishek Sharma 44" ``` ## C# ```cs // C# program to count number of ways // we can form triplets with minimum product. using System; class GFG { // function to calculate number of triples static long noOfTriples(long []arr, int n) { ????// Sort the array ????Array.Sort(arr); ????// Count occurrences of third element ????long count = 0; ????for (int i = 0; i < n; i++)? ????????if (arr[i] == arr[2]) ????????????count++; ????// If all three elements are same (minimum ????// element appears at least 3 times). Answer ????// is nC3\. ????if (arr[0] == arr[2]) ????????return (count - 2) * (count - 1) * (count) / 6; ????// If minimum element appears once.?? ????// Answer is nC2\. ????else if (arr[1] == arr[2]) ????????return (count - 1) * (count) / 2; ????// Minimum two elements are distinct. ????// Answer is nC1\. ????return count; } //driver code public static void Main() { ????long []arr = { 1, 3, 3, 4 }; ????int n = arr.Length; ????Console.Write(noOfTriples(arr, n)); } } //This code is contributed by Anant Agarwal. ``` ## PHP ```php <?php // PHP program to count number of ways? // we can form triplets with minimum // product. // function to calculate number of // triples function noOfTriples( $arr, $n) { ????// Sort the array ????sort($arr); ????// Count occurrences of third element ????$count = 0; ????for ( $i = 0; $i < $n; $i++)? ????????if ($arr[$i] == $arr[2]) ????????????$count++; ????// If all three elements are same? ????// (minimum element appears at least? ????// 3 times). Answer is nC3\. ????if ($arr[0] == $arr[2]) ????????return ($count - 2) * ($count - 1)?? ???????????????????????????* ($count) / 6; ????// If minimum element appears once.? ????// Answer is nC2\. ????else if ($arr[1] == $arr[2]) ????????return ($count - 1) * ($count) / 2; ????// Minimum two elements are distinct. ????// Answer is nC1\. ????return $count; } // Driver code ????$arr = array( 1, 3, 3, 4 ); ????$n = count($arr); ????echo noOfTriples($arr, $n); // This code is contributed by anuj_67\. ?> ``` Output: ``` 1 ``` 時間復雜度：`O(N log N)` 可以通過首先找到最小元素及其頻率，如果頻率小于 3，然后找到第二個最小值及其頻率，來優化解決方案。如果總頻率小于 3，則找到第三個最小值及其頻率。此優化解決方案的時間復雜度為`O(n)` 本文由 [**Sagar Shukla**](https://auth.geeksforgeeks.org/profile.php?user=Sagar Shukla) 貢獻。如果您喜歡 GeeksforGeeks 并希望做出貢獻，則還可以使用 [tribution.geeksforgeeks.org](http://www.contribute.geeksforgeeks.org) 撰寫文章，或將您的文章郵寄至 tribution@geeksforgeeks.org。查看您的文章出現在 GeeksforGeeks 主頁上，并幫助其他 Geeks。