Mức độ của một mảng trong C ++

Giả sử chúng ta có một mảng các số nguyên không âm được gọi là nums, mức độ của mảng này thực sự là tần số lớn nhất của bất kỳ một phần tử nào của nó. Chúng ta phải tìm độ dài nhỏ nhất có thể có của một dãy con nums liền kề, có cùng mức độ với nums.

Vì vậy, nếu đầu vào là [1,2,2,3,1], thì đầu ra sẽ là 2, điều này là do mảng đầu vào có bậc 2 vì cả phần tử 1 và 2 xuất hiện hai lần. Các mảng con có cùng mức độ - [1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2 , 2, 3], [2, 2] Độ dài ngắn nhất là 2. Soanswer sẽ là 2.

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

• Xác định tần suất mảng có kích thước 50000 và điền vào giá trị này bằng 0
• max_:=0
• cho mỗi n trong nums
  • (tăng freq [n] thêm 1)
  • max_:=tối đa max_ và freq [n]
• điền mảng freq bằng 0.
• min_:=kích thước của nums
• để khởi tạo i:=0, j:=-1, size:=size của nums, khi j
• nếu j> =0 và freq [nums [j]] giống với max_ thì -
  • min_:=tối thiểu là min_ và j - i + 1
• ngược lại khi j
• tăng j lên 1
• tăng tần suất [nums [j]] lên 1

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 findShortestSubArray(vector<int>& nums) {
      vector<int> freq(50000, 0);
      int max_ = 0;
      for (const int n : nums)
         max_ = max(max_, ++freq[n]);
      fill(freq.begin(), freq.end(), 0);
      int min_ = nums.size();
      for (int i = 0, j = -1, size = nums.size(); j < size;) {
         if (j >= 0 && freq[nums[j]] == max_)
            min_ = min(min_, j - i + 1), --freq[nums[i++]];
         else if (j < size - 1)
            ++freq[nums[++j]];
         else
         break;
      }
      return min_;
   }
};
main(){
   Solution ob;
   vector<int> v = {1, 2, 2, 3, 1};
   cout << (ob.findShortestSubArray(v));
}

Đầu vào

{1, 2, 2, 3, 1}

Đầu ra

2