leetcode 697 Degree of an Array

zsy888 发布于2019-08-15 14:00 / 1511人阅读

摘要：输入数组的度为因为元素和都出现过两次所有度为的子数组最短的长度为，所以返回。另一个保存元素的值和元素出现的范围，用数组表示，表示第一次出现的位置，表示最后出现的位置。最后遍历，获取满足度相等的最小子数组长度。

题目详情

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

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/68447.html

leetcode 部分解答索引（持续更新～）

摘要：前言从开始写相关的博客到现在也蛮多篇了。而且当时也没有按顺序写现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言从开始写leetcode相关的博客到现在也蛮多篇了。而且当时也没有按顺序写～现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理 1~50 1...

leo108 2019-08-15 14:26 评论0 收藏0
前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：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