Go語言題解LeetCode1051高度檢查器示例詳解
題目描述
學(xué)校打算為全體學(xué)生拍一張年度紀(jì)念照。根據(jù)要求,學(xué)生需要按照 非遞減 的高度順序排成一行。
排序后的高度情況用整數(shù)數(shù)組 expected
表示,其中 expected[i]
是預(yù)計排在這一行中第 i
位的學(xué)生的高度(下標(biāo)從 0
開始)。
給你一個整數(shù)數(shù)組 heights
,表示 當(dāng)前學(xué)生站位 的高度情況。heights[i]
是這一行中第 i
位學(xué)生的高度(下標(biāo)從 0 開始)。
返回滿足 heights[i] != expected[i]
的 下標(biāo)數(shù)量 。
示例:
輸入:heights = [1,1,4,2,1,3] 輸出:3 解釋: 高度:[1,1,4,2,1,3] 預(yù)期:[1,1,1,2,3,4] 下標(biāo) 2 、4 、5 處的學(xué)生高度不匹配。
示例 2:
輸入:heights = [5,1,2,3,4] 輸出:5 解釋: 高度:[5,1,2,3,4] 預(yù)期:[1,2,3,4,5] 所有下標(biāo)的對應(yīng)學(xué)生高度都不匹配。
示例 3:
輸入:heights = [1,2,3,4,5] 輸出:0 解釋: 高度:[1,2,3,4,5] 預(yù)期:[1,2,3,4,5] 所有下標(biāo)的對應(yīng)學(xué)生高度都匹配。
提示:
1 <= heights.length <= 100 1 <= heights[i] <= 100
思路分析
此題不需要最終排序結(jié)果,只需要關(guān)注數(shù)組所在索引和其對應(yīng)的值排序后索引是否一致即可 可以用map保存,key位heights中元素,value位key出現(xiàn)的次數(shù)
最后按i=1,i<=100遍歷一遍map,即可知道heights中每個值對應(yīng)的順序了
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方法,但是考慮到時間復(fù)雜度較高,進(jìn)而采用桶排序方式
木桶長度為所有高度的范圍,初始值為0, 更新木桶數(shù)據(jù)為列表中對應(yīng)高度的頻次,
再依次輸出木桶元素(輸出元素一定是按照非遞減順序),與原列表比較即可確定最小調(diào)換人數(shù)
class Solution(object): def heightChecker(self, heights): #桶排序 不選擇排序是因為時間復(fù)雜度高 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%簡單思路
題目可以簡單的理解為我們將輸入的數(shù)組進(jìn)行升序排序后,再比較數(shù)組變化前后發(fā)生位置變化的元素的個數(shù),那就很簡單了,因為我們排序后要和排序前相比較,所以我們要先復(fù)制一個數(shù)組出來以供排序后使用,然后我對源數(shù)組進(jìn)行升序排序,最后進(jìn)行比較輸出位置變化元素的數(shù)量即可
class Solution { public: int heightChecker(vector<int>& heights) { int num=0; vector<int> p(heights); //復(fù)制一個一模一樣的數(shù)組 sort(heights.begin(),heights.end()); //對源數(shù)組進(jìn)行升序排序 for(int i =0;i<heights.size();i++){ //循環(huán)比較找出位置發(fā)生變化元素的數(shù)量 if(heights[i]!=p[i]){ num++; } } return num; } };
參考
http://www.dbjr.com.cn/article/271252.htm
以上就是Go語言題解LeetCode1051高度檢查器示例詳解的詳細(xì)內(nèi)容,更多關(guān)于Go語言高度檢查器的資料請關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
go gin中間件關(guān)于 c.next()、c.abort()和return的使用小結(jié)
中間件的執(zhí)行順序是按照注冊順序執(zhí)行的,中間件可以通過 c.abort() + retrurn 來中止當(dāng)前中間件,后續(xù)中間件和處理器的處理流程,?這篇文章給大家介紹go gin中間件關(guān)于 c.next()、c.abort()和return的使用小結(jié),感興趣的朋友跟隨小編一起看看吧2024-03-03Golang 函數(shù)執(zhí)行時間統(tǒng)計裝飾器的一個實現(xiàn)詳解
這篇文章主要介紹了Golang 函數(shù)執(zhí)行時間統(tǒng)計裝飾器的一個實現(xiàn)詳解,小編覺得挺不錯的,現(xiàn)在分享給大家,也給大家做個參考。一起跟隨小編過來看看吧2019-03-03Go創(chuàng)建Grpc鏈接池實現(xiàn)過程詳解
這篇文章主要為大家介紹了Go創(chuàng)建Grpc鏈接池實現(xiàn)過程詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-03-03golang使用viper加載配置文件實現(xiàn)自動反序列化到結(jié)構(gòu)
這篇文章主要為大家介紹了golang使用viper加載配置文件實現(xiàn)自動反序列化到結(jié)構(gòu)示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-08-08Go語言題解LeetCode724尋找數(shù)組的中心下標(biāo)
這篇文章主要為大家介紹了Go語言題解LeetCode724尋找數(shù)組的中心下標(biāo),有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2022-12-12