技术提高是一个循序渐进的过程,所以我讲的leetcode算法题从最简单的level开始写的,然后到中级难度,最后到hard难度全部完。
目前我选择C语言,Python和Java作为实现语言,因为这三种语言还是比较典型的。由于篇幅和精力有限,其他语言的实现有兴趣的朋友请自己尝试。
初级难度说的差不多的时候,我打算再加点其他内容,我可能会从操作系统到协议栈,从分布式聊到大数据框架,从大数据聊到人工智能,... ...。
如果有任何问题可以在文章后评论或者私信给我。
我会持续分享下去,敬请您的关注。
LeetCode 697. 数组的度 (Degree of an Array)
问题描述:给定一个非空且只包含非负数的整数数组 nums, 数组的度的定义是指数组里任一元素出现频数的最大值。
你的任务是找到与 nums 拥有相同大小的度的最短连续子数组,返回其长度。
注:
- nums.length 在1到50,000区间范围内。
- nums[i] 是一个在0到49,999范围内的整数。
首先,要知道数组的度,就要统计数组中不同数字出现的数量。这需要遍历整个数组,如示例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.