Given an array arr[] and an integer k, we need to print k maximum elements of given array. The elements should printed in the order of the input.
Note : k is always less than or equal to n.
Examples:
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
Method 1: We search for the maximum element k times in the given array. Each time we find one maximum element, we print it and replace it with minus infinite (INT_MIN in C) in the array. The time complexity of this method is O(n*k).
C++
// C++ program to find k Maximum elements #include <bits/stdc++.h> using namespace std; // Function to print k Maximum elements void printMax(int a[], int n, int k) { int b[n],c[n]; // Coping the array a // into c and initialising // elements in array b as 0. for(int i=0;i<n;i++) { c[i]=a[i]; b[i]=0; } // Iterating for K-times // to find k-maximum for(int i=0;i<k;i++) { // finding the maximum element // and its index int maxi=INT_MIN; int index; for(int j=0;j<n;j++) { if(a[j]>maxi) { maxi=a[j]; index=j; } } // Assigning 1 in order // to mark the position // of all k maximum numbers b[index]=1; a[index]=INT_MIN; } for(int i=0;i<n;i++) { // Printing the k maximum // elements of the array if(b[i]==1) cout<<c[i]<<" "; } } // Driver code int main() { int a[] = { 50, 8, 45, 12, 25, 40, 84 }; int n = sizeof(a) / sizeof(a[0]); int k = 3; printMax(a, n, k); return 0; } // This code is contributed by Aman kumar. |
50 45 84
Time Complexity: O(n*k)
Auxiliary Space: O(n)
Method 2: In this method, we store the original array in a new array and will sort the new array in descending order. After sorting, we iterate the original array from 0 to n and print all those elements that appear in first k elements of new array. For searching, we can do Binary Search.
C++
// C++ 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 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; } |
Output:
50 45 84
Time Complexity: O(n Log n) for sorting.
Auxiliary Space: O(n)
Please refer complete article on Find k maximum elements of array in original order for more details!
