leetcode 697 Degree of an Array

zsy888 發(fā)布于2019-08-15 14:00 / 1551人閱讀

摘要：輸入數(shù)組的度為因為元素和都出現(xiàn)過兩次所有度為的子數(shù)組最短的長度為，所以返回。另一個保存元素的值和元素出現(xiàn)的范圍，用數(shù)組表示，表示第一次出現(xiàn)的位置，表示最后出現(xiàn)的位置。最后遍歷，獲取滿足度相等的最小子數(shù)組長度。

題目詳情

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.

輸入一個正整數(shù)數(shù)組，這個數(shù)組的“度”就是數(shù)組中任意元素出現(xiàn)的最大次數(shù)。而我們要找出這個數(shù)組的一個子數(shù)組，滿足“度”等于整個數(shù)組的“度”的同時，保證子數(shù)組的長度最小，返回這個最小的長度。Example 1:
Input: [1, 2, 2, 3, 1]
Output: 2
Explanation: 
輸入數(shù)組的度為2（因為元素1和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]
最短的長度為2，所以返回2。
Example 2:
Input: [1,2,2,3,1,4,2]
Output: 6

想法

想盡量減少遍歷的次數(shù)，因此在第一趟遍歷中我們即保存了所有元素出現(xiàn)的次數(shù)，也保存了每個元素出現(xiàn)的范圍。

因為涉及到對元素出現(xiàn)次數(shù)的計數(shù)，因此我們采用HashMap來實現(xiàn)。一個HashMap保存元素的值和出現(xiàn)的次數(shù)。另一個Hashmap保存元素的值和元素出現(xiàn)的范圍，用int[] numRange數(shù)組表示，numRange[0]表示第一次出現(xiàn)的位置，numRange[1]表示最后出現(xiàn)的位置。

最后遍歷HashMap，獲取滿足“度”相等的最小子數(shù)組長度。

解法

    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;
    }

GPU云服務器云服務器 Degree Leetcod LeetCode LeetCode_String

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/68447.html

leetcode 部分解答索引（持續(xù)更新～）

摘要：前言從開始寫相關的博客到現(xiàn)在也蠻多篇了。而且當時也沒有按順序?qū)懍F(xiàn)在翻起來覺得蠻亂的?？赡艽蠹铱粗卜浅２环奖恪Ｋ栽谶@里做個索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言從開始寫leetcode相關的博客到現(xiàn)在也蠻多篇了。而且當時也沒有按順序?qū)憽F(xiàn)在翻起來覺得蠻亂的?？赡艽蠹铱粗卜浅２环奖恪Ｋ栽谶@里做個索引嘻嘻。順序整理 1~50 1...

leo108 2019-08-15 14:26 評論0 收藏0
前端 | 每天一個 LeetCode

摘要：在線網(wǎng)站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學習。這篇文章記錄我練習的 LeetCode 題目，語言 JavaScript。在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...

張漢慶 2019-08-23 13:42 評論0 收藏0
[LeetCode] 210. Course Schedule II

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...

zhkai 2019-08-19 11:12 評論0 收藏0
[LeetCode] 642. Design Search Autocomplete System

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...

MartinHan 2019-08-16 13:40 評論0 收藏0
[Leetcode] Course Schedule 課程計劃

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...

Amio 2019-08-14 12:40 評論0 收藏0