Tần số bằng nhau tối đa trong C ++

Giả sử chúng ta có một số mảng là số nguyên dương, chúng ta phải trả về độ dài dài nhất có thể có của tiền tố mảng trong số các số mảng đã cho, sao cho có thể xóa chính xác một phần tử khỏi tiền tố này để mọi số xuất hiện trong đó sẽ có cùng tần số. Sau khi loại bỏ một phần tử nếu không còn phần tử nào, vẫn được coi là mọi số xuất hiện có cùng tần suất (0).

Vì vậy, nếu đầu vào là [3,3,2,2,6,4,4,6], thì đầu ra sẽ là 7, Vì vậy, nếu chúng ta loại bỏ phần tử 6 khỏi chỉ mục 4, thì mảng con sẽ là [3, 3,2,2,4,4] trong đó tất cả các phần tử xuất hiện hai lần.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

maxf:=0, res:=0
Xác định bản đồ cnt và freq
để khởi tạo i:=0, khi tôi
- x:=nums [i]
- (tăng cnt [x] lên 1)
- f:=cnt [x]
- (tăng freq [f] lên 1)
- giảm tần suất [f - 1] xuống 1
- maxf:=tối đa của maxf và f
- nếu maxf * freq [maxf] giống với i hoặc (maxf - 1) * (freq [maxf - 1] + 1) giống với i hoặc maxf giống 1, thì -
  - res:=i + 1
trả lại res

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int maxEqualFreq(vector<int>& nums) {
      int maxf = 0, res = 0;
      map<int, int> cnt, freq;
      for (int i = 0; i < nums.size(); i++) {
         int x = nums[i];
         cnt[x]++;
         int f = cnt[x];
         freq[f]++;
         freq[f - 1]--;
         maxf = max(maxf, f);
         if (maxf * freq[maxf] == i || (maxf - 1) * (freq[maxf - 1] + 1) == i || maxf == 1) {
            res = i + 1;
         }
      }
      return res;
   }
};
main(){
   Solution ob;
   vector<int> v = {3,3,2,2,6,4,4,6};
   cout << (ob.maxEqualFreq(v));
}

Đầu vào

{3,3,2,2,6,4,4,6}

Tần số bằng nhau tối đa trong C ++

Ví dụ

Đầu vào

Đầu ra