正整數數組中 k 個整數的最小積 · GeeksForGeeks 中文系列教程

# 正整數數組中 k 個整數的最小積 > 原文： [https://www.geeksforgeeks.org/minimum-product-k-integers-array-positive-integers/](https://www.geeksforgeeks.org/minimum-product-k-integers-array-positive-integers/) 給定`n`個正整數數組。我們需要編寫一個程序來打印給定數組的`k`個整數的最小乘積。 **示例**： ``` Input : 198 76 544 123 154 675 k = 2 Output : 9348 We get minimum product after multiplying 76 and 123. Input : 11 8 5 7 5 100 k = 4 Output : 1400 ``` 這個想法很簡單，我們找到最小的`k`個元素并打印它們的乘法。在下面的實現中，我們使用了基于[堆](https://www.geeksforgeeks.org/heap-data-structure/)的簡單方法，將數組元素插入到最小堆中，然后找到前`k`個元素的乘積。 ## C++ ```cpp // CPP program to find minimum product of // k elements in an array #include <bits/stdc++.h> using namespace std; int minProduct(int arr[], int n, int k) { ????priority_queue<int, vector<int>, greater<int> > pq; ????for (int i = 0; i < n; i++) ????????pq.push(arr[i]); ????int count = 0, ans = 1; ????// One by one extract items from max heap ????while (pq.empty() == false && count < k) { ????????ans = ans * pq.top(); ????????pq.pop(); ????????count++; ????} ????return ans; } // Driver code int main() { ????int arr[] = {198, 76, 544, 123, 154, 675}; ????int k = 2; ????int n = sizeof(arr) / sizeof(arr[0]); ????cout << "Minimum product is " ?????????<< minProduct(arr, n, k); ????return 0; } ``` ## Java ```java // Java program to find minimum product of? // k elements in an array import java.util.PriorityQueue; class GFG { ????public static int minProduct(int[] arr, int n, int k)? ????{ ????????PriorityQueue<Integer> pq = new PriorityQueue<>(); ????????for (int i = 0; i < n; i++) ????????????pq.add(arr[i]); ????????????int count = 0, ans = 1; ????????????// One by one extract items ????????????while(pq.isEmpty() == false && count < k) ????????????{ ????????????????ans = ans * pq.element(); ????????????????pq.remove(); ????????????????count++; ????????????} ????????????return ans; ????} ????// Driver Code ????public static void main(String[] args) ????{ ????????int arr[] = {198, 76, 544, 123, 154, 675}; ????????int k = 2; ????????int n = arr.length; ????????System.out.print("Minimum product is " +? ??????????????????????????minProduct(arr, n, k)); ????} } // This code is contributed by sanjeev2552 ``` ## Python3 ```py # Python3 program to find minimum # product of k elements in an array import math? import heapq def minProduct(arr, n, k): ????heapq.heapify(arr) ????count = 0 ????ans = 1 ????# One by one extract? ????# items from min heap ????while ( arr ) and count < k: ????????x = heapq.heappop(arr) ????????ans = ans * x ????????count = count + 1 ????return ans; # Driver method arr = [198, 76, 544, 123, 154, 675] k = 2 n = len(arr) print ("Minimum product is", ???????minProduct(arr, n, k)) ``` **輸出**： ``` Minimum product is 9348 ``` **時間復雜度**：`O(n * log n)` 請注意，可以使用[這里](https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array-set-2-expected-linear-time/)和[這里](https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array-set-3-worst-case-linear-time/)討論的方法在`O(n)`時間內解決上述問題。