C ++中数组的度数

假设我们有一个称为nums的非负整数数组,该数组的次数实际上就是其任何元素的最大频率。我们必须找到连续的子数组num的最小可能长度,该子数组与num的度数相同。

因此,如果输入类似于[1,2,2,3,1],则输出将为2,这是因为输入数组的次数为2,因为元素1和2都出现了两次。具有相同度数的子数组-[1、2、2、3、1],[1、2、2、3],[2、2、3、1],[1、2、2],[2 ,2,3],[2,2]最短的长度是2。因此答案将是2。

为了解决这个问题,我们将遵循以下步骤-

  • 定义大小为50000的数组频率,并用0填充

  • max_:= 0

  • 每n个数字

    • (将freq [n]增加1)

    • max_:= max_和freq [n]的最大值

  • 用0填充freq数组。

  • min_:= nums的大小

  • 对于初始化i:= 0,j:= -1,size:= nums的大小,当j <size时,执行-

    • 从循环中出来

    • 将j增加1

    • 将freq [nums [j]]增加1

    • min_:= min_和j的最小值-i + 1

    • 如果j> = 0并且freq [nums [j]]与max_相同,则-

    • 否则,当j <size-1时,则-

    • 除此以外

    • 返回min_

    让我们看下面的实现以更好地理解-

    示例

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

    输入值

    {1, 2, 2, 3, 1}

    输出结果

    2