LeetCode 687配列の度HERODINGのLeetCodeの道
非空で非負数のみを含む整数配列numsを与え、配列の度の定義は指数群のいずれかの要素の出現周波数の最大値である.
あなたの任務はnumsの中でnumsと同じ大きさの度を持つ最短連続サブ配列を見つけて、その長さを返すことです.
例1:
入力:[1,2,2,3,1]出力:2解釈:入力配列の度は2であり、要素1と2の出現周波数が最大であるため、いずれも2である.連続サブ配列の中に同度を持つものは、[1,2,2,3,1],[1,2,2,3],[2,2,3,[2,3,1],[1,2,2],[2,2,3],[2,2]最短連続サブ配列[2,2]の長さが2であるため、2を返す.
例2:
入力:[1,2,2,3,1,4,2]出力:6
ヒント:
ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/degree-of-an-array著作権はインターネットの所有に帰属する.商業転載は公式の授権に連絡してください.非商業転載は出典を明記してください.
問題を解く構想:まず問題の意味を分析して、目的は全体の配列の最大の数字の周波数と同じサブ配列の長さを見つけることで、つまり私達は1つの最も短いウィンドウを構築して、全体のウィンドウはある数字の周波数が全体の配列の最大の数字の周波数に等しいことを満たして、それでは問題は刃を迎えて解いて、先にmapで数字の個数と最大の周波数を統計する限り、再び配列全体を巡り、スライドウィンドウで制限し、最も短い条件を満たすウィンドウの長さを見つければいい.注釈はすでに詳しく、コードは以下の通りである.
あなたの任務はnumsの中でnumsと同じ大きさの度を持つ最短連続サブ配列を見つけて、その長さを返すことです.
例1:
入力:[1,2,2,3,1]出力:2解釈:入力配列の度は2であり、要素1と2の出現周波数が最大であるため、いずれも2である.連続サブ配列の中に同度を持つものは、[1,2,2,3,1],[1,2,2,3],[2,2,3,[2,3,1],[1,2,2],[2,2,3],[2,2]最短連続サブ配列[2,2]の長さが2であるため、2を返す.
例2:
入力:[1,2,2,3,1,4,2]出力:6
ヒント:
nums.length 1 50,000 。
nums[i] 0 49,999 。
ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/degree-of-an-array著作権はインターネットの所有に帰属する.商業転載は公式の授権に連絡してください.非商業転載は出典を明記してください.
問題を解く構想:まず問題の意味を分析して、目的は全体の配列の最大の数字の周波数と同じサブ配列の長さを見つけることで、つまり私達は1つの最も短いウィンドウを構築して、全体のウィンドウはある数字の周波数が全体の配列の最大の数字の周波数に等しいことを満たして、それでは問題は刃を迎えて解いて、先にmapで数字の個数と最大の周波数を統計する限り、再び配列全体を巡り、スライドウィンドウで制限し、最も短い条件を満たすウィンドウの長さを見つければいい.注釈はすでに詳しく、コードは以下の通りである.
class Solution {
public:
int findShortestSubArray(vector<int>& nums) {
//
unordered_map<int, int> mp;
int max_fre = 0;
// ,
for(int i = 0; i < nums.size(); i ++) {
mp[nums[i]] ++;
max_fre = max(max_fre, mp[nums[i]]);
}
// map
mp.erase(mp.begin(), mp.end());
//
int ans = nums.size();
int left = 0, right = 0;
while(right < nums.size()) {
mp[nums[right]] ++;
// ,
while(mp[nums[right]] == max_fre) {
ans = min(ans, right - left + 1);
mp[nums[left ++]] --;
}
right ++;
}
return ans;
}
};
/* :heroding
:https://leetcode-cn.com/problems/degree-of-an-array/solution/maphua-dong-chuang-kou-czui-yi-li-jie-si-e7fw/
: (LeetCode)
。 , 。*/