-
Notifications
You must be signed in to change notification settings - Fork 1
/
degree_of_array.py
77 lines (60 loc) · 1.94 KB
/
degree_of_array.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#!/usr/bin/env python3
def occ(a):
d = {}
for i in range(len(a)):
if a[i] not in d:
d[a[i]] = 1
else:
d[a[i]] += 1
return d # This dictionary count the occurrence of each number in input array
def m_d(d):
max = 0
for v in diz.values():
if v > max :
max = v
lo = []
for k,v in diz.items():
if v == max:
lo.append(k) # list of the element that occurs most frequently input in array
print("\nThe most frequent numbers: ", lo, " - Each occurs: ",max," time")
return lo, max
def scorr(arr,lo,maxd):
arr2 = []
for i in range(len(arr)):
if arr[i] in lo:
lo.remove(arr[i])
sub_arr= []
cont = 0
for j in range(i,len(arr)):
if arr[j] == arr[i]:
cont += 1
sub_arr.append(arr[j])
if cont == maxd:
break
arr2.append(sub_arr)
return arr2 # This is the list of the shortest sub-arrays that share the degree("max")
arr = [3,1,2,3,4,78,1,1,2,2]
arr2 = [7,25,7,3,25,4,5,6,9,8,8,9]
arr3 = [1,1,1,1,1,9,1,1]
diz = occ(arr)
#print(diz) #{3: 2, 1: 3, 2: 3, 4: 1, 78: 1} #
lo,maxd = m_d(diz)
print("The shortest sub-arrays that share array degree:")
print(scorr(arr,lo,maxd))
#The most frequent numbers: [1, 2] - Each occurs: 3 time
#The shortest sub-arrays that share array degree:
#[[1, 2, 3, 4, 78, 1, 1], [2, 3, 4, 78, 1, 1, 2, 2]]
diz = occ(arr2)
lo,maxd = m_d(diz)
print("The shortest sub-arrays that share array degree:")
print(scorr(arr2,lo,maxd))
#The most frequent numbers: [7, 25, 9, 8] - Each occurs: 2 time
#The shortest sub-arrays that share array degree:
#[[7, 25, 7], [25, 7, 3, 25], [9, 8, 8, 9], [8, 8]]
diz = occ(arr3)
lo,maxd = m_d(diz)
print("The shortest sub-arrays that share array degree:")
print(scorr(arr3,lo,maxd))
#The most frequent numbers: [1] - Each occurs: 7 time
#The shortest sub-arrays that share array degree:
#[[1, 1, 1, 1, 1, 9, 1, 1]]