資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++陣列的度
假設我們有一個名為nums的非負整數陣列，該陣列的度實際上是其任何一個元素的最大頻率。我們必須找到nums的具有相同度的連續子陣列的最小可能長度。
因此，如果輸入類似於[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的陣列freq並將其填充為0
- max_ := 0
- 對於nums中的每個n
- (將freq[n]增加1)
- max_ := max_和freq[n]中的最大值
- 將freq陣列填充為0。
- min_ := nums的大小
- 初始化i := 0，j := -1，size := nums的大小，當j < size時，執行：
- 如果j >= 0且freq[nums[j]]與max_相同，則：
- min_ := min_和j - i + 1中的最小值
- 否則，當j < size - 1時，則：
- 將j增加1
- 將freq[nums[j]]增加1
- 否則
- 退出迴圈
- 如果j >= 0且freq[nums[j]]與max_相同，則：
- 返回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
更新於：2020年7月4日
521 次瀏覽
廣告