資訊專欄INFORMATION COLUMN
摘要：輸入數(shù)組的度為因?yàn)樵睾投汲霈F(xiàn)過兩次所有度為的子數(shù)組最短的長(zhǎng)度為，所以返回。另一個(gè)保存元素的值和元素出現(xiàn)的范圍，用數(shù)組表示，表示第一次出現(xiàn)的位置，表示最后出現(xiàn)的位置。最后遍歷，獲取滿足度相等的最小子數(shù)組長(zhǎng)度。
題目詳情
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.
輸入一個(gè)正整數(shù)數(shù)組，這個(gè)數(shù)組的“度”就是數(shù)組中任意元素出現(xiàn)的最大次數(shù)。而我們要找出這個(gè)數(shù)組的一個(gè)子數(shù)組，滿足“度”等于整個(gè)數(shù)組的“度”的同時(shí)，保證子數(shù)組的長(zhǎng)度最小，返回這個(gè)最小的長(zhǎng)度。想法Example 1:
Input: [1, 2, 2, 3, 1]
Output: 2
Explanation:
輸入數(shù)組的度為2（因?yàn)樵?和2都出現(xiàn)過兩次）
所有度為2的子數(shù)組：
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
最短的長(zhǎng)度為2，所以返回2。
Example 2:
Input: [1,2,2,3,1,4,2]
Output: 6
想盡量減少遍歷的次數(shù)，因此在第一趟遍歷中我們即保存了所有元素出現(xiàn)的次數(shù)，也保存了每個(gè)元素出現(xiàn)的范圍。
因?yàn)樯婕暗綄?duì)元素出現(xiàn)次數(shù)的計(jì)數(shù)，因此我們采用HashMap來實(shí)現(xiàn)。一個(gè)HashMap保存元素的值和出現(xiàn)的次數(shù)。另一個(gè)Hashmap保存元素的值和元素出現(xiàn)的范圍，用int[] numRange數(shù)組表示，numRange[0]表示第一次出現(xiàn)的位置，numRange[1]表示最后出現(xiàn)的位置。
最后遍歷HashMap，獲取滿足“度”相等的最小子數(shù)組長(zhǎng)度。
解法 public int findShortestSubArray(int[] nums) {
int minLength = nums.length;
int degree = 0;
HashMap count = 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;
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/68447.html
摘要：前言從開始寫相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時(shí)也沒有按順序?qū)懍F(xiàn)在翻起來覺得蠻亂的?？赡艽蠹铱粗卜浅２环奖?。所以在這里做個(gè)索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新 前言 從開始寫leetcode相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時(shí)也沒有按順序?qū)憽F(xiàn)在翻起來覺得蠻亂的?？赡艽蠹铱粗卜浅２环奖?。所以在這里做個(gè)索引嘻嘻。 順序整理 1~50 1...
摘要：在線網(wǎng)站地址我的微信公眾號(hào)完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個(gè)題。這是項(xiàng)目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目，語言 JavaScript。 在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號(hào)： 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...
閱讀 1968·2021-11-15 11:46
閱讀 1183·2021-10-26 09:49
閱讀 1915·2021-10-14 09:42
閱讀 3450·2021-09-26 09:55
閱讀 895·2019-08-30 13:58
閱讀 1116·2019-08-29 16:40
閱讀 3546·2019-08-26 10:27
閱讀 670·2019-08-23 18:18
