Students are asked to stand in non-decreasing order of heights for an annual photo.
Return the minimum number of students not standing in the right positions. (This is the number of students that must move in order for all students to be standing in non-decreasing order of height.)
Example 1:
Input: [1,1,4,2,1,3] Output: 3 Explanation: Students with heights 4, 3 and the last 1 are not standing in the right positions.
Note:
1 <= heights.length <= 1001 <= heights[i] <= 100
Solution: Sorting
Time complexity: O(nlogn)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 |
class Solution { public: int heightChecker(vector<int>& heights) { vector<int> h(heights); sort(begin(h), end(h)); int ans = 0; for (int i = 0; i < h.size(); ++i) ans += (heights[i] != h[i]); return ans; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment