Go語言題解LeetCode1051高度檢查器範例詳解

2022-12-29 14:00:57

題目描述

學校打算為全體學生拍一張年度紀念照。根據要求，學生需要按照 非遞減 的高度順序排成一行。

排序後的高度情況用整數陣列 expected 表示，其中 expected[i] 是預計排在這一行中第 i 位的學生的高度（下標從 0 開始）。

給你一個整數陣列 heights ，表示當前學生站位的高度情況。heights[i] 是這一行中第 i 位學生的高度（下標從 0 開始）。

返回滿足 heights[i] != expected[i]的下標數量。

範例：

輸入：heights =&nbsp;[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://www.jb51.net/article/271252.htm

以上就是Go語言題解LeetCode1051高度檢查器範例詳解的詳細內容，更多關於Go語言高度檢查器的資料請關注it145.com其它相關文章！