```C++
#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <random>
#include <chrono>
#include <iomanip>
class FrequencyAnalyzer {
private:
// Custom comparator for min-heap of pairs
struct CompareFrequency {
bool operator()(const std::pair<int, int>& a, const std::pair<int, int>& b) {
return a.first > b.first; // Min heap based on frequency
}
};
public:
static std::vector<int> generateRandomNumbers(int n = 10000, int min = 1, int max = 1000) {
std::vector<int> numbers(n);
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<> dis(min, max);
for (int i = 0; i < n; i++) {
numbers[i] = dis(gen);
}
return numbers;
}
static std::vector<std::pair<int, int>> findTopKFrequent(const std::vector<int>& numbers, int k = 10) {
// Count frequencies
std::unordered_map<int, int> frequencyMap;
for (int num : numbers) {
frequencyMap[num]++;
}
// Use min heap to keep top k frequencies
std::priority_queue<std::pair<int, int>,
std::vector<std::pair<int, int>>,
CompareFrequency> heap;
for (const auto& pair : frequencyMap) {
heap.push({pair.second, pair.first});
if (heap.size() > k) {
heap.pop();
}
}
// Extract results in descending order
std::vector<std::pair<int, int>> result;
while (!heap.empty()) {
result.insert(result.begin(), heap.top());
heap.pop();
}
return result;
}
};
int main() {
// Generate random numbers
std::cout << "Generating 10000 random numbers...\n";
auto numbers = FrequencyAnalyzer::generateRandomNumbers();
// Measure execution time
auto start = std::chrono::high_resolution_clock::now();
// Find top 10 frequencies
auto topFrequencies = FrequencyAnalyzer::findTopKFrequent(numbers);
auto end = std::chrono::high_resolution_clock::now();
auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
// Print results
std::cout << "\nTop 10 most frequent numbers:\n";
std::cout << std::setw(12) << "Number" << std::setw(12) << "Frequency\n";
std::cout << std::string(24, '-') << '\n';
for (const auto& pair : topFrequencies) {
std::cout << std::setw(12) << pair.second
<< std::setw(12) << pair.first << '\n';
}
// Print timing and complexity analysis
std::cout << "\nExecution time: " << duration.count() << " microseconds\n\n";
std::cout << "Complexity Analysis:\n";
std::cout << "--------------------\n";
std::cout << "Time Complexity:\n";
std::cout << "- Counting frequencies: O(n)\n";
std::cout << "- Building/maintaining heap: O(m log k) where m is unique numbers\n";
std::cout << "- Overall: O(n + m log k)\n\n";
std::cout << "Space Complexity:\n";
std::cout << "- Hash map: O(m) where m is unique numbers\n";
std::cout << "- Heap: O(k)\n";
std::cout << "- Overall: O(m)\n\n";
// Calculate approximate memory usage
size_t vectorSize = numbers.size() * sizeof(int);
size_t mapSize = topFrequencies.size() * (sizeof(int) * 2);
size_t heapSize = 10 * sizeof(std::pair<int, int>);
std::cout << "Approximate Memory Usage:\n";
std::cout << "- Input vector: " << vectorSize / 1024.0 << " KB\n";
std::cout << "- Frequency map: " << mapSize / 1024.0 << " KB\n";
std::cout << "- Heap: " << heapSize / 1024.0 << " KB\n";
return 0;
}
```
Output:
Generating 10000 random numbers...
Top 10 most frequent numbers:
Number Frequency
------------------------
867 22
88 22
386 21
879 21
49 21
290 21
1000 20
70 20
849 20
637 19
Execution time: 1411 microseconds
Complexity Analysis:
--------------------
Time Complexity:
- Counting frequencies: O(n)
- Building/maintaining heap: O(m log k) where m is unique numbers
- Overall: O(n + m log k)
Space Complexity:
- Hash map: O(m) where m is unique numbers
- Heap: O(k)
- Overall: O(m)
Approximate Memory Usage:
- Input vector: 39.0625 KB
- Frequency map: 0.078125 KB
- Heap: 0.078125 K