C++의 배열 차수

<시간/>

nums라고 하는 음이 아닌 정수 배열이 있다고 가정하고 이 배열의 차수는 실제로 해당 요소 중 하나의 최대 빈도입니다. nums와 같은 차수를 가진 nums의 연속 하위 배열에서 가능한 가장 작은 길이를 찾아야 합니다.

따라서 입력이 [1,2,2,3,1]과 같으면 출력이 2가 됩니다. 이는 요소 1과 2가 모두 두 번 나타나기 때문에 입력 배열의 차수가 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으로 채웁니다.
최대_ :=0
nums의 각 n에 대해
- (freq[n] 1씩 증가)
- max_ :=max_ 및 freq[n]의 최대값
주파수 배열을 0으로 채웁니다.
min_ :=숫자 크기
초기화 i :=0, j :=-1, 크기 :=숫자 크기, j <크기일 때 −
- j>=0이고 freq[nums[j]]가 max_와 같으면 -
  - min_ :=min_ 및 j의 최소값 - i + 1
- 그렇지 않으면 j
- 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}