26. Line-up Mismatch
A school photographer wants the students in a row ordered from shortest to tallest, left to right. Students with the same height may stand in any order among themselves. The students are currently standing in the order given by the array heights, and the photographer wants to know how many of them are not yet in the right place.
Write a method heightMismatches that takes the array heights and returns the number of positions i where heights[i] differs from the height that would stand at position i in the correctly ordered row.
Example 1
- Input:
- heights = [1,1,4,2,1,3]
- Output:
- 3
- Explanation:
The ordered row is 1, 1, 1, 2, 3, 4. Positions 2, 4 and 5 differ from the current row, so the answer is 3.
Example 2
- Input:
- heights = [1,2,3,4,5]
- Output:
- 0
- Explanation:
The row is already ordered, so no one is out of place.
Constraints
1 ≤ heights.length ≤ 1000
1 ≤ heights[i] ≤ 100
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n log n)
- Space
- O(n)