［抄題］：

Given a non-empty array of non-negative integers?nums, the?degree?of this array is defined as the maximum frequency of any one of its elements.

Your task is to find the smallest possible length of a (contiguous) subarray of?nums, that has the same degree as?nums.

Example 1:

Input: [1, 2, 2, 3, 1] Output: 2 Explanation: The input array has a degree of 2 because both elements 1 and 2 appear twice. Of the subarrays that have the same degree: [1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2] The shortest length is 2. So return 2.

?

Example 2:

Input: [1,2,2,3,1,4,2] Output: 6

?[暴力解法]：

時間分析：

空間分析：

?[優化后]：

時間分析：

空間分析：

［奇葩輸出條件］：

［奇葩corner case］：

［思維問題］：

讀題不懂

［一句話思路］：

先統計，再比較

［輸入量］：空：?正常情況：特大：特小：程序里處理到的特殊情況：異常情況（不合法不合理的輸入）：

［畫圖］：

［一刷］：

數字一般初始化為整數中相反的最大或者最小值，忘了

忘了 檢查key用的是containsKey方法

［二刷］：

［三刷］：

［四刷］：

［五刷］：

? [五分鐘肉眼debug的結果]：

［總結］：

有很多指標，所以用多維數組+hashmap來實現

［復雜度］：Time complexity: O(n) Space complexity: O(n)

［英文數據結構或算法，為什么不用別的數據結構或算法］：

某數字 最大值的 最小覆蓋范圍， 有很多指標，所以用多維數組+hashmap來實現

hashmap可以用for(: .values())冒號表達式把所有值取出來

［關鍵模板化代碼］：

［其他解法］：

［Follow Up］：

［LC給出的題目變變變］：

?[代碼風格] ：

put中直接寫數值 不能再賦值，所以new int[]{直接跟數組即可}

class Solution {public int findShortestSubArray(int[] nums) {//ccif (nums == null || nums.length == 0) {return 0;}//iniHashMap<Integer, int[]> map = new HashMap<>();//collect into hashmapfor (int i = 0; i < nums.length; i++) {if (!map.containsKey(nums[i])) {map.put(nums[i], new int[]{1, i, i});//val, first index, last index}else {int temp[] = map.get(nums[i]);temp[0] += 1;temp[2] = i;map.put(nums[i], temp);}}//compare//bigger degree//same degree but smaller range//ini to the extremeint degree = Integer.MIN_VALUE;int result = Integer.MAX_VALUE;for (int[] val : map.values()) {if (val[0] > degree) {degree = val[0];result = val[2] - val[1] + 1;}else {if (val[0] == degree) {result = Math.min(result, val[2] - val[1] + 1);}}}//returnreturn result;} } View Code

?

轉載于:https://www.cnblogs.com/immiao0319/p/8875741.html

總結

以上是生活随笔為你收集整理的697. Degree of an Array 频率最高元素的最小覆盖子数组的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。