Students are asked to stand in non-decreasing order of heights for an annual photo.

Return the minimum number of students that must move in order for all students to be standing in non-decreasing order of height.

Notice that when a group of students is selected they can reorder in any possible way between themselves and the non selected students remain on their seats.

Example 1:

Input: heights = [1,1,4,2,1,3]
Output: 3
Explanation:
Current array : [1,1,4,2,1,3]
Target array  : [1,1,1,2,3,4]
On index 2 (0-based) we have 4 vs 1 so we have to move this student.
On index 4 (0-based) we have 1 vs 3 so we have to move this student.
On index 5 (0-based) we have 3 vs 4 so we have to move this student.

Example 2:

Input: heights = [5,1,2,3,4]
Output: 5

Example 3:

Input: heights = [1,2,3,4,5]
Output: 0

Constraints:

  • 1 <= heights.length <= 100
  • 1 <= heights[i] <= 100

这道题说是有一群学生随机的站成一排照相,现在想让学生按照身高来排列,问需要移动
多个同学。这是一道很简单的题目没有什么难度,只要复制一个新的数组,然后给数组排序,再跟原数组逐个按数字来对比,只要数字不同,则结果 res 自增1即可,参见代码如下:


class Solution {
public:
	int heightChecker(vector<int>& heights) {
		int res = 0, n = heights.size();
		vector<int> sorted = heights;
		sort(sorted.begin(), sorted.end());
		for (int i = 0; i < n; ++i) {
		  	if (sorted[i] != heights[i]) ++res;
		}
		return res;
	}
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1051


参考资料:

https://leetcode.com/problems/height-checker/

https://leetcode.com/problems/height-checker/discuss/299221/C%2B%2B-Sort

https://leetcode.com/problems/height-checker/discuss/299216/Java-Sort-1ms-O(nlogn)


标签智能推荐:

LeetCode高频题目(100)汇总-Java实现

&nbsp;LeetCode高频题目(100)汇总-Java实现&nbsp;&nbsp;&nbsp;【Leetcode-easy-1】TwoSum【Leetcode-easy-2】AddTwoNumbers【Leetcode-easy-3】LongestSubstringWithoutRepeatingCharacters【Leetcode-easy-5】LongestPalindromicSub

C++ 前期准备

在线编译网站:http://www.dooccn.com/cpp/刷题:https://leetcode.com/https://leetcode-cn.com/

Index

Tableofcontents目录TableofcontentsOJ-Improvemyself,better.Leetcode洛谷OJ-Improvemyself,better.Leetcode洛谷

Leetcode 真题

字符串493https://leetcode-cn.com/problems/longest-substring-without-repeating-characters30https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words49https://leetcode-cn.com/problems/grou

算法-1

1.能少for循环,就少2.与for无关的变量的不进入for循环刷题网址:1.leetcode:https://leetcode.cn/https://leetcode-cn.com/2.牛客网:https://www.nowcoder.com/

8.2

python版按键精灵,pyautogui。未完成,看书deeplearning,刷题leetcode。明日:网络脚本,看书,刷题。

二分搜索常见题

LeetCode:1011.在D天内送达包裹的能力&nbsp;https://leetcode-cn.com/problems/capacity-to-ship-packages-within-d-days/875.爱吃香蕉的珂珂&nbsp;https://leetcode-cn.com/problems/koko-eating-bananas/1482.制作m束花所需的最少天数&nbsp;htt

09-06日记

1.leetcode复习五道2.你不知道的js学习3.webpack学习

总结-二叉树

二叉树:前序遍历:https://leetcode-cn.com/problems/binary-tree-preorder-traversal/中序遍历:https://leetcode-cn.com/problems/binary-tree-inorder-traversal/后序遍历:https://leetcode-cn.com/problems/binary-tree-postorder

11-29日记

1.leetcode两道2.koa源码学习3.跨域知识学习