【LeetCode】697. Degree of an Array 解题报告
2024-09-01 20:09:01
【LeetCode】697. Degree of an Array 解题报告
标签(空格分隔): LeetCode
题目地址: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:
Input: [1, 2, 2, 3, 1]
Output: 2
Explanation:
The input array has a degree of 2 because both elements 1 and 2 appear twice.
Of the subarrays that have the same degree:
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
The shortest length is 2. So return 2.
Example 2:
Input: [1,2,2,3,1,4,2]
Output: 6
Note:
- nums.length will be between 1 and 50,000.
- nums[i] will be an integer between 0 and 49,999.
Ways
方法一:
题目大意:
给定非空非负整数数组,数组的度是指元素的最大出现次数。
寻找最大连续区间,使得区间的度与原数组的度相同。
想法很粗暴,直接求出整个数组的degree,然后找出所有的度等于该degree的数,找出最小度的数。
import collections
class Solution(object):
def findShortestSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) == len(set(nums)):
return 1
counter = collections.Counter(nums)
degree_num = counter.most_common(1)[0]
most_numbers = [num for num in counter if counter[num] == degree_num[1]]
scale = 100000000
for most_number in most_numbers:
appear = [i for i,num in enumerate(nums) if num == most_number]
appear_scale = max(appear) - min(appear) + 1
if appear_scale < scale:
scale = appear_scale
return scale
上面使用了Counter,下面的直接数,速度有一点提高。
import collections
class Solution(object):
def findShortestSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
nums_set = set(nums)
if len(nums) == len(nums_set):
return 1
degree = max([nums.count(num) for num in nums_set])
most_numbers = [num for num in nums_set if nums.count(num) == degree]
scale = 100000000
for most_number in most_numbers:
appear = [i for i,num in enumerate(nums) if num == most_number]
appear_scale = max(appear) - min(appear) + 1
if appear_scale < scale:
scale = appear_scale
return scale
上面的不够快是因为重复计算了多次的nums.count(num),避免重复计算可以使用字典进行保存。这个方法超出了96.7%的提交。
import collections
class Solution(object):
def findShortestSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
nums_set = set(nums)
if len(nums) == len(nums_set):
return 1
num_dict = {num:nums.count(num) for num in nums_set}
degree = max(num_dict.values())
most_numbers = [num for num in nums_set if num_dict[num] == degree]
scale = 100000000
for most_number in most_numbers:
appear = [i for i,num in enumerate(nums) if num == most_number]
appear_scale = max(appear) - min(appear) + 1
if appear_scale < scale:
scale = appear_scale
return scale
还能更快吗?可以。把能压缩的列表表达式拆开,这样迭代一次就可以了。最后用了个提前终止,如果scale==degree
说明这段子列表里没有其他元素了,一定是最短的。
这个方法超过了99.91%的提交。
import collections
class Solution(object):
def findShortestSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
nums_set = set(nums)
if len(nums) == len(nums_set):
return 1
num_dict = {}
degree = -1
for num in nums_set:
_count = nums.count(num)
num_dict[num] = _count
if _count > degree:
degree = _count
most_numbers = [num for num in nums_set if num_dict[num] == degree]
scale = 100000000
for most_number in most_numbers:
_min = nums.index(most_number)
for i in xrange(len(nums)-1, -1, -1):
if nums[i] == most_number:
_max = i
break
appear_scale = _max - _min + 1
if appear_scale < scale:
scale = appear_scale
if scale == degree:
break
return scale
Date
2018 年 1 月 23 日
最新文章
- JAXP简介
- 关于JavaScript定时机制的总结
- 开发微信App支付
- oracle dblink的创建方式
- java和android及IOS对接RSA加密经验
- shell流程控制语句
- CSDN 夏令营课程 项目分析
- 强制性输出private中变量的三种方法
- 使用HttpClient进行Get方式通信
- 安装oracle11g client 【INS-30131】执行安装程序验证所需的初始设置失败的解决方法
- 使用 Resharper 快速做适配器
- bootbox.js官方文档中文版
- Linux:wc命令详解
- Android中的关于MDM中的几个方法举例
- Docker删除全部镜像和容器
- GetWindowRect和GetClientRect比较学习
- Jmeter测试接口简单使用教程
- CodeVS 1503 愚蠢的宠物
- 【Luogu】P4234最小差值生成树(LCT)
- Decorator Pattern
热门文章
- C#数字验证
- Mybatis相关知识点(一)
- 大数据学习day15----第三阶段----scala03--------1.函数(“_”的使用, 函数和方法的区别)2. 数组和集合常用的方法(迭代器,并行集合) 3. 深度理解函数 4 练习(用java实现类似Scala函数式编程的功能(不能使用Lambda表达式))
- 【leetcode】563. Binary Tree Tilt
- 【leetcode】212.&#160;Word Search II
- PhoneGap打包webApp
- virtualBox 系统移植
- 匿名内部类与lamda表达式
- 回溯——51. N皇后
- 干掉visio,这个画图神器太香了