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
|
# 1051. Height Checker
"""
a school is trying to take an annual photo of all the students. the students
are asked to stand in a single file line in non decreasing order by height.
let this ordering be represented by the integer array 'expected' where
'expected[i]' is the expected height of the i'th student in line. you are
given an integer array 'heights' representing the current order that the
students are standing in. each 'heights[i]' is the height of the i'th student
in line. return the number of indices where 'heights[i] != expected[i]'
"""
class Solution(object):
def heightChecker(self, heights):
"""
:type heights: List[int]
:rtype: int
"""
max_nr = max(heights)
cnt = [0] * (max_nr + 1)
for n in heights:
cnt[n] += 1
sum_cnt = [0] * (max_nr + 1)
for i, n in enumerate(cnt[1:], start=1):
sum_cnt[i] = n + sum_cnt[i - 1]
output = [0] * len(heights)
for i in range(len(heights) - 1, -1, -1):
output[sum_cnt[heights[i]] - 1] = heights[i]
sum_cnt[heights[i]] -= 1
ans = 0
for i, n in enumerate(heights):
if n != output[i]:
ans += 1
return ans
if __name__ == "__main__":
obj = Solution()
print(obj.heightChecker(heights=[1, 1, 4, 2, 1, 3]))
print(obj.heightChecker(heights=[5, 1, 2, 3, 4]))
print(obj.heightChecker(heights=[1, 2, 3, 4, 5]))
|