ความถี่ที่เท่ากันสูงสุดใน C++

สมมติว่าเรามีจำนวนอาร์เรย์ที่เป็นจำนวนเต็มบวก เราต้องคืนค่าความยาวที่ยาวที่สุดของคำนำหน้าอาร์เรย์ของจำนวนอาร์เรย์ที่กำหนด เพื่อให้สามารถลบองค์ประกอบหนึ่งตัวออกจากคำนำหน้านี้ได้ เพื่อให้ทุกตัวเลขที่ปรากฏอยู่ มีความถี่เท่ากัน หลังจากลบองค์ประกอบหนึ่งรายการแล้วหากไม่มีองค์ประกอบเหลือ จะยังถือว่าทุกหมายเลขที่ปรากฏมีความถี่เท่ากัน (0)

ดังนั้น หากอินพุตเป็น [3,3,2,2,6,4,4,6] เอาต์พุตจะเป็น 7 ดังนั้นหากเราลบองค์ประกอบ 6 ออกจากดัชนี 4 อาร์เรย์ย่อยจะเป็น [3, 3,2,2,4,4] โดยที่องค์ประกอบทั้งหมดปรากฏขึ้นสองครั้ง

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• maxf :=0, res :=0

• กำหนดแผนที่ cnt และความถี่

• สำหรับการเริ่มต้น i :=0 เมื่อ i <ขนาดของ nums ให้อัปเดต (เพิ่ม i ขึ้น 1) ให้ทำ -

  • x :=nums[i]

  • (เพิ่ม cnt[x] ขึ้น 1)

  • f :=cnt[x]

  • (เพิ่มความถี่[f] ขึ้น 1)

  • ลดความถี่[f - 1] ลง 1

  • maxf :=สูงสุดของ maxf และ f

  • ถ้า maxf * freq[maxf] เหมือนกับ i หรือ (maxf - 1) * (freq[maxf - 1] + 1) เหมือนกับ i หรือ maxf เหมือนกับ 1 ดังนั้น −

    • res :=i + 1

• ผลตอบแทน

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#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));
}

อินพุต

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

ผลลัพธ์

7