首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Leetcode 697. Degree of an Array

Leetcode 697. Degree of an Array

作者头像
Tyan
发布2021-03-02 16:30:26
2820
发布2021-03-02 16:30:26
举报
文章被收录于专栏:SnailTyanSnailTyan

文章作者:Tyan 博客:noahsnail.com | CSDN | 简书

1. Description

Degree of an Array
Degree of an Array

2. Solution

  • Version 1
from collections import Counter
class Solution:
    def findShortestSubArray(self, nums):
        stat = Counter(nums)
        degree = 0
        result = len(nums)
        for key, value in stat.items():
            if value > degree:
                degree = value

        for key, value in stat.items():
            if value == degree:
                left = 0
                right = len(nums) - 1
                while nums[left] != key or nums[right] != key:
                    if nums[left] != key:
                        left += 1
                    if nums[right] != key:
                        right -= 1
                sub_length = right - left + 1
                if result > sub_length:
                    result = sub_length
        return result
  • Version 2
from collections import Counter
class Solution:
    def findShortestSubArray(self, nums):
        stat = Counter(nums)
        degree = 0
        result = len(nums)
        for key, value in stat.items():
            if value > degree:
                degree = value

        for index, value in enumerate(nums):
            if value in stat and stat[value] == degree:
                end = len(nums) - 1
                while nums[end] != value:
                    end -= 1
                sub_length = end - index + 1
                del stat[value]
                if result > sub_length:
                    result = sub_length
        return result
  • Version 3
class Solution:
    def findShortestSubArray(self, nums):
        degree = 0
        result = len(nums)
        stat = {}
        for index, value in enumerate(nums):
            if value in stat:
                stat[value]['degree'] += 1
                stat[value]['end'] = index
            else:
                stat[value] = {'degree': 1, 'start': index, 'end': index}

            sub_length = stat[value]['end'] - stat[value]['start'] + 1
            if stat[value]['degree'] > degree:
                degree = stat[value]['degree']
                result = sub_length
            if stat[value]['degree'] == degree and sub_length < result:
                result = sub_length

        return result
  • Version 4
class Solution:
    def findShortestSubArray(self, nums):
        degree = 0
        result = len(nums)
        stat = {}
        for index, value in enumerate(nums):
            if value in stat:
                stat[value]['degree'] += 1
            else:
                stat[value] = {'degree': 1, 'start': index}

            sub_length = index - stat[value]['start'] + 1
            if stat[value]['degree'] > degree:
                degree = stat[value]['degree']
                result = sub_length
            elif stat[value]['degree'] == degree and sub_length < result:
                result = sub_length

        return result

Reference

  1. https://leetcode.com/problems/degree-of-an-array/
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2021-02-22 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1. Description
  • 2. Solution
  • Reference
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档