Detailed explanation of the Go language problem solution LeetCode1051 height inspector example

Question description

1051. Height Inspector - LeetCode

The school plans to take an annual commemorative photo for all students. As required, students need to followNon-decreasingThe height order is arranged in a row.

Use an integer array for sorting heightsexpectedIndicates thatexpected[i]It is expected to be ranked in this lineiThe height of the student (subscript from0start).

Give you an array of integersheights, indicating the current height of the student position.heights[i]It's the first in this lineistudent height (subscript starts at 0).

Return to satisfyheights[i] != expected[i]The number of subscripts of .

Example:

enter：heights = [1,1,4,2,1,3]
Output：3 
explain：
high：[1,1,4,2,1,3]
expected：[1,1,1,2,3,4]
Subscript 2 、4 、5 处的学生high不匹配。

Example 2:

enter：heights = [5,1,2,3,4]
Output：5
explain：
high：[5,1,2,3,4]
expected：[1,2,3,4,5]
所有下标的对应学生high都不匹配。

Example 3:

enter：heights = [1,2,3,4,5]
Output：0
explain：
high：[1,2,3,4,5]
expected：[1,2,3,4,5]
所有下标的对应学生high都匹配。

hint:

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

Idea Analysis

This question does not require the final sorting result, you only need to pay attention to whether the index where the array is located and its corresponding value is sorted. You can save it with map, the number of times the key appears in the key bit heights, and the value bit key appears.

Finally, press i=1, i<=100 to traverse the map, and you will know the order of each value in heights.

AC Code

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 
}

Height Inspector Bucket Sort

The sorted method was initially used, but considering the high time complexity, the bucket sorting method was used.
The length of the barrel is a range of all heights, the initial value is 0, and the update bucket data is the frequency of the corresponding height in the list.
Then output the barrel elements in sequence (the output elements must be in non-decreasing order), and compare them with the original list to determine the minimum number of substitutions.

class Solution(object):
    def heightChecker(self, heights):
        #Bucket sorting The order is not selected because of the high time complexity        bucket = [0]*101 #Height range 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% simple idea to beat 100% in time

The question can be simply understood as we sort the input array in ascending order, and then compare the number of elements that have changed positions before and after the array changes. That is very simple, because after sorting, we need to compare it with before sorting, so we need to copy an array for sorting, and then I sort the source array in ascending order, and finally compare the number of elements that have changed positions.

class Solution {
public:
    int heightChecker(vector<int>& heights) {
        int num=0;
        vector<int> p(heights);               //Copy an identical array        sort((),());  //Sort the source array ascending order        for(int i =0;i<();i++){   // Loop comparison to find out the number of elements that have changed positions            if(heights[i]!=p[i]){
                num++;
            }
        } 
        return num;
    }
};

refer to

https:///article/

The above is the detailed explanation of the LeetCode1051 height inspector example for Go language problem solving. For more information about Go language height inspector, please pay attention to my other related articles!