1051. 高度检查器

LeetCode - 1051. 高度检查器


题目描述

难度:简单

学校打算为全体学生拍一张年度纪念照。根据要求,学生需要按照 非递减 的高度顺序排成一行。

排序后的高度情况用整数数组 expected 表示,其中 expected[i] 是预计排在这一行中第 i 位的学生的高度(下标从 0 开始)。

给你一个整数数组 heights ,表示 当前学生站位 的高度情况。heights[i] 是这一行中第 i 位学生的高度(下标从 0 开始)。

返回满足 heights[i] != expected[i] 的 下标数量 。

示例 1:

输入:heights = [1,1,4,2,1,3]
输出:3 
解释:
高度:[1,1,4,2,1,3]
预期:[1,1,1,2,3,4]
下标 2 、4 、5 处的学生高度不匹配。

示例 2:

输入:heights = [5,1,2,3,4]
输出:5
解释:
高度:[5,1,2,3,4]
预期:[1,2,3,4,5]
所有下标的对应学生高度都不匹配。

提示:

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

分析

题目很长,结合题目和示例可以分析出题目的大体意思,就是一个无序数组将它排序后,移动元素的个数;或者说是排序后数组与原数组元素一一对应之后,不一样元素的个数。
理解清楚以后,解题思路就很清晰,对数组进行排序,之后遍历数组进行对比。

代码:

public static int heightChecker(int[] heights) {

        int[] ints = heights.clone();
        Arrays.sort(heights);
        int result = 0;
        for (int i = 0; i < heights.length; i++) {
            if(ints[i] != heights[i]){
                ++result;
            }
        }

        return result;
    }

在leetcode上跑了之后,发现效率和内存占用情况都不太好,就去翻阅了一下评论,发现了一个更有效的写法,利用桶排序来完成;

解题思路:由于题目说 1 <= heights[i] <= 100 也就是数组元素最大不超过100,那么我们可以创建长度为 101 的数组,然后将原数组中的元素作为下标,在创建数组中利用这些下标来存储每一个元素的出现次数。

	int[] bucket = new int[101];
    for (int height : heights) {
        bucket[height]++;  // 索引heigth位置的元素加一
    }

之后从头遍历数组( bucket ),利用储存的值来确定原数组中的对应下标的元素是否符合要求 ( 比如桶数组中下标为 0 的桶 值为 0 ,下标为 1 的桶 值为 2,那么原数组中索引 0 和 1 的位置的值必须是 1 )。( 结合桶排序更好理解)

代码:

public int heightChecker(int[] heights) {
        int result = 0;
        int[] b = new int[101];
        for (int height : heights) {
            b[height]++;  // 索引heigth位置的元素加一
        }

        for(int i = 1, j = 0; i < b.length ; i++){
            while (b[i]-- > 0){
                if(heights[j++] != i) result++; 
            }
        }

        return result;
    }

总结

第一种解法简单,理解题目意思后很好解决;第二种需要理解桶排序的概念,利用桶数组来规定原数组中元素出现的顺序与次数。



岁月悠悠,衰微只及肌肤;热忱抛却,颓废必致灵魂

上一篇:2021必修 CSS架构系统精讲


下一篇:leetcode 85. Maximal Rectangle | 85. 最大矩形(单调栈)