LeetCode 697. 数组的度 (Degree of an Array)
问题描述:
给定一个非空且只包含 非负数 的整数数组 nums, 数组的度的定义是指数组里任一元素出现 频数 的最大值。
你的任务是找到与 nums 拥有相同大小的度的最短连续子数组,返回其长度。
注:
- nums.length 在1到50,000区间范围内。
- nums[i] 是一个在0到49,999范围内的整数。
示例:
C语言实现:
首先,要知道数组的度,就要统计数组中不同数字出现的数量。这需要遍历整个数组,如示例1,数组中元素1和2出现的次数都是2,所以度是2。
再次,连续子数组度和原数组要相同,按照实例我们很容易知道所谓的“最短连续子数组”就是 相同的频数最大元素的左边第一个到最右边最后一个这段连续元素组成的数组中最短的那个 。如果觉得拗口,请看下面举例说明:
在示例1中,元素1和元素2都是频度最大的元素,元素1的最左边到最右边组成的数组是[1,2,2,3,1],元素2的最左边到最右边组成的数组是[2,2],最后[2,2]作为最短连续子数组。
我们可以将这两个步骤放在一起处理。
代码如下:
我们定义了两个长度是50000的数组,来分别统计不同数字在数组中出现的次数,以及不同数字第一次出现的”位置”。然后开始遍历数组。
(50000的长度是因为题目中对数组元素范围进行了限制,不过50000的长度对于这种算法来说确实不小了。)
代码第6行,统计不同数字出现的次数。
如果该数字第一次出现,那么存储它的位置,注意我们这里存储的是下标加1,主要是为了避免下标为0的情况下的额外处理。
如果该数字不是第一次出现,那么会进入代码10~16这段逻辑中。首先我们计算当前连续数组长度,这个长度是该数字的起始下标到当前位置的长度,是一个闭区间,即包含该数字本身。注意这个长度只是临时的,如果后面该数字再次出现,这个长度就会再次变大。
如果当前该数字出现的次数大于当前已知的”数组的度”,那么显然当前数字将是当前已知的频数最大的元素,当前该数字的计数也将会被作为新的”数组的度”(注意在数组没遍历结束之前,这个度都不是最终的度),并且我们我们要将前面获取的len赋值给minLen,它的用途在代码14~16行,当出现另一个最大频数的时候,如示例1那样情况,我们就需要比较哪一个连续子数组长度最短。我们将最短的重新赋值给minLen
通过以上的逻辑最终minLen获得的就是最短连续子数组的长度。
这里注意一种特殊情况,如果数组的度是1,即所有元素都仅出现一次,那么minLen应该返回1,所以minLen的初始值我们设置为1.
python语言的实现:
我们根据nums生成一个Couter对象,在通过most_common方法,将其转换成一个元组列表。
这个列表安装元素出现的个数有序排列的,其中出现次数最大的在最前面。c[0][1]就是频数最大的元素出现的次数,即数组的度,如前所述,如果度为1,直接返回1。
否则我们通过列表生成器生成一个列表entries,它是所有频数最大的元素组成的列表,因为最短连续子数组也仅仅与它们有关。
然后我们开始遍历entries,分别求出它们的最短连续子数组的长度,然后取其最小值即可。
代码如下:
Java语言的实现:
Java实现和C语言基本一致,具体描述请参考上面C语言的部分。
代码如下: