1.題目
給定一個非空且只包含非負數的整數陣列 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, 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
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
2.暴力破解
這一次沒有做出優良的解法，所以寫了個暴力破解，就是每一個數依次比較，找出出現次數最大且長度最短的符合題意得元素，回傳長度即可
int findShortestSubArray(vector<int>& nums) {
int left = 0;
int minlength = 1;
int maxsum = 1;
while(left < nums.size() - 1) {
int right = left + 1;
int sum = 1;
int length = 1;
while(right < nums.size()) {
if(nums[right] == nums[left]) {
sum++;
length = right - left + 1;
}
right++;
}
if(sum > maxsum) {
maxsum = sum;
minlength = length;
}
else if((sum == maxsum) && (length < minlength)) {
maxsum = sum;
minlength = length;
}
left++;
}
return minlength;
}
3.利用哈希表
想到用哈希表了，但并不知道如何應用到這個題目中，多做一些哈希表的值，
3.1 原理
我們可以利用哈希表，把出現的數字統計一下，用一個長度為3的陣列記錄出現的次數，最初出現的位置，最后出現的位置，這樣我們就可以求出次數最多并且長度最短的了，
3.2代碼
class Solution {
public:
int findShortestSubArray(vector<int>& nums) {
unordered_map<int, vector<int>> mp;
int n = nums.size();
for (int i = 0; i < n; i++) {
if (mp.count(nums[i])) {
mp[nums[i]][0]++;
mp[nums[i]][2] = i;
} else {
mp[nums[i]] = {1, i, i};
}
}
int maxNum = 0, minLen = 0;
for (auto& [_, vec] : mp) {
if (maxNum < vec[0]) {
maxNum = vec[0];
minLen = vec[2] - vec[1] + 1;
} else if (maxNum == vec[0]) {
if (minLen > vec[2] - vec[1] + 1) {
minLen = vec[2] - vec[1] + 1;
}
}
}
return minLen;
}
};
作者：LeetCode-Solution
鏈接：https://leetcode-cn.com/problems/degree-of-an-array/solution/shu-zu-de-du-by-leetcode-solution-ig97/
來源：力扣（LeetCode）
著作權歸作者所有，商業轉載請聯系作者獲得授權，非商業轉載請注明出處，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/261657.html
標籤：其他