fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <unordered_map>
  4. #include <queue>
  5. using namespace std;
  6.  
  7. vector<int> distributeElements(vector<int>& nums, int d) {
  8.     int n = nums.size();
  9.  
  10.     unordered_map<int, int> mp;
  11.     priority_queue<pair<int, int>> pq; // {frequency, element}
  12.  
  13.     // Count frequency of each element
  14.     for (int i = 0; i < n; ++i) {
  15.         mp[nums[i]]++;
  16.     }
  17.  
  18.     // Push elements into max heap based on frequency
  19.     for (auto& it : mp) {
  20.         pq.push({it.second, it.first});
  21.     }
  22.  
  23.     int windowSz = d + 1;
  24.     vector<int> ans(n);
  25.  
  26.     // Fill the first 'd' elements with highest frequency elements
  27.     for (int i = 0; i < d && !pq.empty(); ++i) {
  28.         int eleFreq = pq.top().first;
  29.         int ele = pq.top().second;
  30.         pq.pop();
  31.  
  32.         ans[i] = ele;
  33.         eleFreq--;
  34.         mp[ele]--;
  35.  
  36.         if (mp[ele] == 0) {
  37.             mp.erase(ele);
  38.         } else {
  39.             pq.push({eleFreq, ele}); // push back with updated frequency
  40.         }
  41.     }
  42.  
  43.     // Fill the rest of the array
  44.     for (int i = d; i < n; ++i) {
  45.         ans[i] = ans[i - windowSz];
  46.         mp[ans[i]]--;
  47.  
  48.         if (mp[ans[i]] == 0) {
  49.             mp.erase(ans[i]);
  50.         }
  51.     }
  52.  
  53. 	// if(mp.size() > 0) return vector<int> ();
  54.  
  55.     return ans;
  56. }
  57.  
  58. int main() {
  59.     vector<int> nums = {1, 1, 2, 2, 3, 3, 4, 5}; // Example input
  60.     int d = 2;
  61.  
  62.     vector<int> result = distributeElements(nums, d);
  63.  
  64. 	// if(result.size() == 0) {
  65. 	// 	cout << -1 << endl;
  66. 	// 	return 0;
  67. 	// }
  68.  
  69.     for (int val : result) {
  70.         cout << val << " ";
  71.     }
  72.     cout << endl;
  73.  
  74.     return 0;
  75. }
  76.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
3 2 0 3 2 0 3 2
https://ideone.com/PJXiS1
language:
C++14 (gcc 8.3)
created:
5 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!