Giả sử chúng ta có một mảng nums các số nguyên dương, chúng ta phải trả về độ dài dài nhất có thể của một tiền tố của mảng nums cho trước, sao cho có thể xóa chính xác một phần tử từ tiền tố này để mọi số đã xuất hiện trong đó sẽ có cùng tần suất. Sau khi xóa 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 giống như [3,3,2,2,6,4,4,6], thì đầu ra sẽ là 7, Vì nếu chúng ta xóa phần tử 6 tại chỉ số 4, thì mảng con sẽ là [3,3,2,2,4,4] nơi tất cả các phần tử xuất hiện hai lần.
Để giải quyết bài toán này, chúng ta sẽ làm theo các bước sau −
maxf := 0, res := 0
Định nghĩa map cnt và freq
for khởi tạo i := 0, khi i < kích thước của nums, cập nhật (tăng i lên 1), thực hiện −
x := nums[i]
(tăng cnt[x] lên 1)
f := cnt[x]
(tăng freq[f] lên 1)
giảm freq[f - 1] xuống 1
maxf := max của maxf và f
nếu maxf * freq[maxf] bằng i hoặc (maxf - 1) * (freq[maxf - 1] + 1) bằng i hoặc maxf bằng 1, thì −
res := i + 1
trả về res
Hãy xem 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} Đầu ra
7