diff options
Diffstat (limited to 'height_checker.py')
-rw-r--r-- | height_checker.py | 42 |
1 files changed, 42 insertions, 0 deletions
diff --git a/height_checker.py b/height_checker.py new file mode 100644 index 0000000..8443737 --- /dev/null +++ b/height_checker.py @@ -0,0 +1,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])) |