fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. #include <vector>
  5. #include <queue>
  6. #include <unordered_map>
  7.  
  8. std::vector<double> findMeanForLastNElementsExcludingTopK(const std::vector<int>& arr, int lastN, int k) {
  9.     if (lastN <= k || arr.empty()) {
  10.         return {};  // Return empty vector for invalid input
  11.     }
  12.  
  13.     int sum_n = 0, sum_k = 0;
  14.     std::vector<double> result;
  15.     std::priority_queue<int, std::vector<int>, std::greater<int>> pq;
  16.     std::unordered_map<int, int> to_remove;
  17.  
  18.     // Process first window of size lastN
  19.     for (int i = 0; i < lastN; ++i) {
  20.         sum_n += arr[i];
  21.         if (pq.size() < k) {
  22.             sum_k += arr[i];
  23.             pq.push(arr[i]);
  24.         } else if (arr[i] > pq.top()) {
  25.             sum_k += arr[i] - pq.top();
  26.             pq.pop();
  27.             pq.push(arr[i]);
  28.         }
  29.     }
  30.  
  31.     result.push_back(static_cast<double>(sum_n - sum_k) / (lastN - k));
  32.  
  33.     // Process rest of the stream
  34.     for (size_t i = lastN; i < arr.size(); ++i) {
  35.         // Remove oldest element from the window
  36.         int oldest = arr[i - lastN];
  37.         sum_n += arr[i] - oldest;
  38.  
  39.         if (oldest >= pq.top()) {
  40.             sum_k -= oldest;
  41.             to_remove[oldest]++;
  42.         }
  43.  
  44.         // Add new element
  45.         if (pq.size() < k) {
  46.             pq.push(arr[i]);
  47.             sum_k += arr[i];
  48.         } else if (arr[i] > pq.top()) {
  49.             sum_k += arr[i] - pq.top();
  50.             pq.pop();
  51.             pq.push(arr[i]);
  52.         }
  53.  
  54.         // Remove elements from priority queue that are no longer in the window
  55.         while (!pq.empty() && to_remove.count(pq.top())) {
  56.             if (--to_remove[pq.top()] == 0) {
  57.                 to_remove.erase(pq.top());
  58.             }
  59.             pq.pop();
  60.         }
  61.  
  62.         result.push_back(static_cast<double>(sum_n - sum_k) / (lastN - k));
  63.     }
  64.  
  65.     return result;
  66. }
  67.  
  68. int main() {
  69. 	// your code goes here
  70.  
  71. 	vector<int> input = {20, 2, -2, 0, 10, 1, 5, -2, 0};
  72. 	vector<double> ans = findMeanForLastNElementsExcludingTopK(input, 5,2);
  73.  
  74. 	for(auto x: ans) {
  75. 		cout<<x<<" ";
  76. 	}
  77.  
  78. 	return 0;
  79. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 0.333333 1.33333 1.33333 1.33333
https://ideone.com/FQzlNF
language:
C++ (gcc 8.3)
created:
44 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!