C++での配列の次数

numsと呼ばれる非負の整数の配列があるとすると、この配列の次数は、実際にはその要素のいずれかの最大頻度です。 numsと同じ次数を持つ、numsの連続するサブ配列の可能な限り最小の長さを見つける必要があります。

したがって、入力が[1,2,2,3,1]の場合、出力は2になります。これは、要素1と2の両方が2回出現するため、入力配列の次数が2であるためです。同じ次数を持つサブ配列-[1、2、2、3、1]、[1、2、2、3]、[2、2、3、1]、[1、2、2]、[2 、2、3]、[2、2]最短の長さは2です。Soanswerは2になります。

これを解決するには、次の手順に従います-

• サイズ50000の配列頻度を定義し、これを0で埋めます
• max_：=0
• numsの各nに対して
  • （freq [n]を1増やします）
  • max_：=max_とfreq[n]の最大値
• 周波数配列を0で埋めます。
• min_：=numsのサイズ
• 初期化i：=0、j：=-1、size：=numsのサイズの場合、j を実行します。
• j> =0で、freq [nums [j]]がmax_と同じである場合、-
  • min_：=min_とjの最小値-i+ 1
• それ以外の場合、j <サイズ-1の場合、-
  • jを1増やします
  • freq[nums[j]]を1増やします
• それ以外の場合
  • ループから抜け出す

理解を深めるために、次の実装を見てみましょう-

例

#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