Leetcode 697. Degree of an Array

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

1. Description

Degree of an Array

2. Solution

  • Version 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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/
如果有收获,可以请我喝杯咖啡!