X

LEETCODE 1051. Height Checker 解题思路分析

题目大意:

高度检查器

学校在拍年度纪念照时,一般要求学生按照 非递减 的高度顺序排列。

请你返回至少有多少个学生没有站在正确位置数量。该人数指的是:能让所有学生以 非递减 高度排列的必要移动人数。

示例:

输入:[1,1,4,2,1,3]
输出:3
解释:
高度为 4、3 和最后一个 1 的学生,没有站在正确的位置。

提示:

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

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1051

解题思路分析:

这是一道简单题目,要求正序排序,然后求出需要移动位置的元素个数。最简单直接的办法就是copy一份原数组,将其排序,查看排序后有多少元素与原数组位置不同即可。

完整代码:

public int heightChecker(int[] heights) {
    int res =0; // 定义返回值
    int[] copy = new int[heights.length]; // 拷贝一个数组
    System.arraycopy(heights, 0, copy, 0, heights.length);
    Arrays.sort(copy); // 排序数组
    for(int i=0;i<heights.length;i++){ // 与原数组比较
        if(heights[i]!=copy[i]){ // 只要元素不相同,结果加一
            res++;
        }
    }
    return res;
}

本题解法执行时间为1ms。

Runtime: 1 ms, faster than 86.08% of Java online submissions for Height Checker.

Memory Usage: 34.7 MB, less than 100.00% of Java online submissions for Height Checker.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1051-height-checker-解题思路分析/
Categories: leetcode
kwantong: