-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathmaxequalfreq.py
More file actions
78 lines (66 loc) · 2.22 KB
/
Copy pathmaxequalfreq.py
File metadata and controls
78 lines (66 loc) · 2.22 KB
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
78
# https://leetcode.com/problems/maximum-equal-frequency/
#
# Notes:
# 1. The number of resubmissions needed corresponds exactly to the number of special cases not considered
from collections import Counter
from typing import List
class Solution:
def __init__(self, debug=False):
self.debug = debug
def sol(self, c: Counter) -> bool:
if self.debug:
print(f"counter {c}")
c_vals = Counter(c.values())
if self.debug:
print(f"c_vals {c_vals}")
if len(c_vals) == 2: # standard case to look for, two different counts appear
a, b = c_vals.keys()
if a > b:
a, b = b, a
if self.debug:
print(f"a,b {a} {b}")
if (a + 1 == b and c_vals[b] == 1) or (a == 1 and c_vals[a] == 1):
if self.debug:
print("True")
return True
elif len(c_vals) == 1 and list(c.values())[0] == 1: # every number occurs once
return True
elif len(c) == 1: # only one number appears
return True
if self.debug:
print("False")
return False
def maxEqualFreq(self, nums: List[int]) -> int:
c = Counter(nums)
idx = len(nums)
while idx > 1 and not self.sol(c):
idx -= 1
if c[nums[idx]] == 1:
del c[nums[idx]]
else:
c[nums[idx]] -= 1
return idx
def test1():
nums = [2, 2, 1, 1, 5, 3, 3, 5]
assert Solution(True).maxEqualFreq(nums) == 7
def test2():
nums = [1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5]
assert Solution(True).maxEqualFreq(nums) == 13
def test3():
nums = [1, 1, 1, 2, 2, 2]
assert Solution().maxEqualFreq(nums) == 5
def test4():
nums = [10, 2, 8, 9, 3, 8, 1, 5, 2, 3, 7, 6]
assert Solution(True).maxEqualFreq(nums) == 8
def test5():
# failed test on initial submission
nums = [1,2]
assert Solution(True).maxEqualFreq(nums) == 2
def test6():
# failed test on second submission
nums = [1,1]
assert Solution(True).maxEqualFreq(nums) == 2
def test7():
# failed test on third submission
nums = [1,2,3,4,5,6,7,8,9]
assert Solution(True).maxEqualFreq(nums) == 9