摘要:輸入數組的度為因為元素和都出現過兩次所有度為的子數組最短的長度為,所以返回。另一個保存元素的值和元素出現的范圍,用數組表示,表示第一次出現的位置,表示最后出現的位置。最后遍歷,獲取滿足度相等的最小子數組長度。
題目詳情
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:
輸入數組的度為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。
Example 2:
Input: [1,2,2,3,1,4,2]
Output: 6
想盡量減少遍歷的次數,因此在第一趟遍歷中我們即保存了所有元素出現的次數,也保存了每個元素出現的范圍。
因為涉及到對元素出現次數的計數,因此我們采用HashMap來實現。一個HashMap保存元素的值和出現的次數。另一個Hashmap保存元素的值和元素出現的范圍,用int[] numRange數組表示,numRange[0]表示第一次出現的位置,numRange[1]表示最后出現的位置。
最后遍歷HashMap,獲取滿足“度”相等的最小子數組長度。
解法public int findShortestSubArray(int[] nums) { int minLength = nums.length; int degree = 0; HashMapcount = new HashMap (); HashMap index = new HashMap (); for(int i=0;i entry : count.entrySet()){ if(entry.getValue() != degree){ continue; } Integer[] range = index.get(entry.getKey()); minLength = Math.min(minLength, range[1]-range[0]+1); } return minLength; }
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規(guī)行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/68447.html
摘要:前言從開始寫相關的博客到現在也蠻多篇了。而且當時也沒有按順序寫現在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新 前言 從開始寫leetcode相關的博客到現在也蠻多篇了。而且當時也沒有按順序寫~現在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。 順序整理 1~50 1...
摘要:在線網站地址我的微信公眾號完整題目列表從年月日起,每天更新一題,順序從易到難,目前已更新個題。這是項目地址歡迎一起交流學習。 這篇文章記錄我練習的 LeetCode 題目,語言 JavaScript。 在線網站:https://cattle.w3fun.com GitHub 地址:https://github.com/swpuLeo/ca...我的微信公眾號: showImg(htt...
Problem There are a total of n courses you have to take, labeled from 0 to n-1. Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as...
Problem Design a search autocomplete system for a search engine. Users may input a sentence (at least one word and end with a special character #). For each character they type except #, you need to r...
Course Schedule I There are a total of n courses you have to take, labeled from 0 to n - 1.Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is e...
閱讀 1887·2021-11-15 11:46
閱讀 1077·2021-10-26 09:49
閱讀 1819·2021-10-14 09:42
閱讀 3374·2021-09-26 09:55
閱讀 827·2019-08-30 13:58
閱讀 1024·2019-08-29 16:40
閱讀 3462·2019-08-26 10:27
閱讀 601·2019-08-23 18:18