亲宝软件园·资讯

展开

Go语言题解LeetCode1051高度检查器示例详解

刘09k11 人气:0

题目描述

1051. 高度检查器 - 力扣(LeetCode)

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

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

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

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

示例:

输入: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]
所有下标的对应学生高度都不匹配。

示例 3:

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

提示:

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

思路分析

此题不需要最终排序结果,只需要关注数组所在索引和其对应的值排序后索引是否一致即可 可以用map保存,key位heights中元素,value位key出现的次数

最后按i=1,i<=100遍历一遍map,即可知道heights中每个值对应的顺序了

AC 代码

func heightChecker(heights []int) int {
    m := make(map[int]int, 100)
    for i:=0; i<len(heights); i++ {
        if _,ok := m[heights[i]]; ok {
            m[heights[i]]++
        } else {
            m[heights[i]]=1
        }
    }
    var count int
    var j int
    for i:=1; i<=100; i++ {
        if v,ok := m[i]; ok {
            for k:=1;k<=v;k++ {
                if heights[j] != i  {
                    count++
                }
                j++
            }
        }
    }
    return count 
}

高度检查器 桶排序

最初采用sorted方法,但是考虑到时间复杂度较高,进而采用桶排序方式
木桶长度为所有高度的范围,初始值为0, 更新木桶数据为列表中对应高度的频次,
再依次输出木桶元素(输出元素一定是按照非递减顺序),与原列表比较即可确定最小调换人数

class Solution(object):
    def heightChecker(self, heights):
        #桶排序 不选择排序是因为时间复杂度高
        bucket = [0]*101 #身高范围1-100
        for h in heights:
            bucket[h] += 1
        count = 0
        j = 0
        max_height = max(heights)
        for i in range(1,max_height+1):
            while bucket[i] != 0 and j < len(heights):
                if i != heights[j]:
                    count += 1
                bucket[i] -=1
                j += 1   
        return count

用时击败100%简单思路

题目可以简单的理解为我们将输入的数组进行升序排序后,再比较数组变化前后发生位置变化的元素的个数,那就很简单了,因为我们排序后要和排序前相比较,所以我们要先复制一个数组出来以供排序后使用,然后我对源数组进行升序排序,最后进行比较输出位置变化元素的数量即可

class Solution {
public:
    int heightChecker(vector<int>& heights) {
        int num=0;
        vector<int> p(heights);               //复制一个一模一样的数组
        sort(heights.begin(),heights.end());  //对源数组进行升序排序
        for(int i =0;i<heights.size();i++){   //循环比较找出位置发生变化元素的数量
            if(heights[i]!=p[i]){
                num++;
            }
        } 
        return num;
    }
};

参考

https:

加载全部内容

相关教程
猜你喜欢
用户评论