Leetcode Degree of an Array

继续刷题。已经解出来了,需要组织一下思路,明天更。

参考:https://leetcode.com/problems/degree-of-an-array/description/

一、题目

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:

Example 2:

Note:

  • nums.length will be between 1 and 50,000.
  • nums[i] will be an integer between 0 and 49,999.

二、解答

首先要读懂题目。本题要求给定一个非空非负的整数数组,先求出数组的“度”(也就是出现次数最多的那个数字的出现次数),然后找出这个数组的最小连续子数组并返回子数组的长度,要求这个子数组的度和原数组的度相同。

这些子数组都有相同的度:

选取一个长度最小的数组,也就是[2, 2],结果为2。

现在我们要想一想,如何记录整个数组中的数字出现的次数呢?使用HashMap是很好的选择。除此之外,我们要知道出现这些数字出现在哪里(方便统计最小子数组的长度),这就需要另外的一个数组用来记录数字的在数组中的index(最开始的出现位置index1和最末尾出现位置index2,子数组的长度就为index2 – index1 + 1)。

于是可以这样进行设计:HashMap(num[i],int[]{该数的位置信息和出现次数}),最后对HashMap进行遍历即可。

DegreeOAnArrayDay4.java

运行结果为:

三、解答

一道使用HashMap记录数字出现信息的典型题目,可以自由选择记录的方式。一开始做这道题我想了很久脑子都没转过来,可以说是非常菜了,唉。

发表评论

电子邮件地址不会被公开。 必填项已用*标注