以原始順序查找數組的 k 個最大元素 · GeeksForGeeks 中文系列教程

# 以原始順序查找數組的 k 個最大元素 > 原文： [https://www.geeksforgeeks.org/find-k-maximum-elements-array-original-order/](https://www.geeksforgeeks.org/find-k-maximum-elements-array-original-order/) 給定一個數組 arr []和一個整數 k，我們需要打印給定數組的 k 個最大元素。元素應按輸入順序打印。 **注意**： k 始終小于或等于 n。例子： ``` Input : arr[] = {10 50 30 60 15} k = 2 Output : 50 60 The top 2 elements are printed as per their appearance in original array. Input : arr[] = {50 8 45 12 25 40 84} k = 3 Output : 50 45 84 ``` **方法 1**：我們在給定數組中搜索最大元素 k 次。每次找到一個最大元素時，我們都會打印該元素，并在數組中使用負無窮大（在 C 中為 INT_MIN）重新放置它。該方法的時間復雜度為 O（n * k）。 **方法 2**：在此方法中，我們將原始數組存儲在一個新數組中，并將按降序對新數組進行排序。排序后，我們將原始數組從 0 迭代到 n，并打印出現在新數組的前 k 個元素中的所有那些元素。對于搜索，我們可以執行[二分搜索](http://www.geeksforgeeks.org/binary-search/)。 ## C++ ```cpp // CPP program to find k maximum elements? // of array in original order #include <bits/stdc++.h> using namespace std; // Function to print m Maximum elements void printMax(int arr[], int k, int n) { ????// vector to store the copy of the ????// original array ????vector<int> brr(arr, arr + n); ????// Sorting the vector in descending ????// order. Please refer below link for ????// details ????// https://www.geeksforgeeks.org/sort-c-stl/ ????sort(brr.begin(), brr.end(), greater<int>()); ????// Traversing through original array and ????// printing all those elements that are ????// in first k of sorted vector. ????// Please refer https://goo.gl/44Rwgt ????// for details of binary_search() ????for (int i = 0; i < n; ++i) ????????if (binary_search(brr.begin(), ?????????????????brr.begin() + k, arr[i],? ????????????????????????greater<int>())) ????????????cout << arr[i] << " "; } // Driver code int main() { ????int arr[] = { 50, 8, 45, 12, 25, 40, 84 }; ????int n = sizeof(arr) / sizeof(arr[0]); ????int k = 3; ????printMax(arr, k, n); ????return 0; } ``` ## Java ```java // Java program to find k maximum?? // elements of array in original order import java.util.Arrays; import java.util.Collections; public class GfG { ????// Function to print m Maximum elements ????public static void printMax(int arr[], int k, int n) ????{ ????????// Array to store the copy? ????????// of the original array ????????Integer[] brr = new Integer[n]; ????????for (int i = 0; i < n; i++) ????????brr[i] = arr[i]; ????????// Sorting the array in? ????????// descending order ????????Arrays.sort(brr, Collections.reverseOrder()); ????????// Traversing through original array and ????????// printing all those elements that are ????????// in first k of sorted array. ????????// Please refer https://goo.gl/uj5RCD ????????// for details of Arrays.binarySearch() ????????for (int i = 0; i < n; ++i) ????????????if (Arrays.binarySearch(brr, arr[i],? ????????????????????Collections.reverseOrder()) >= 0 ?????????????????&& Arrays.binarySearch(brr, arr[i],? ????????????????????Collections.reverseOrder()) < k) ????????????????System.out.print(arr[i]+ " "); ????} ????// Driver code ????public static void main(String args[]) ????{ ????????int arr[] = { 50, 8, 45, 12, 25, 40, 84 }; ????????int n = arr.length; ????????int k = 3; ????????printMax(arr, k, n); ????} } // This code is contributed by Swetank Modi ``` Output : ``` 50 45 84 ``` 時間復雜度：`O(N log N)`用于排序。輔助空間：`O(n)` * * * * * *