1051. Height Checker

發表於 | 分類於

problem

solution

option 1 - sorting

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int heightChecker(vector<int>& heights) {
        vector<int> expected = heights;
        sort(expected.begin(),expected.end());
        int count =0, n= expected.size();
        for(int i=0;i<n;++i){
            if(expected[i]!=heights[i]) count++;
        }
        return count;
    }
};

option 2 - counting sorted

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int heightChecker(vector<int>& heights) {
        vector<int> count(101, 0);
        for(int h:heights) count[h]++;
        int ret = 0, i=1, n=heights.size();
        for(int j = 0;j<n;++j){
            while(count[i]==0) i++;
            if(i!= heights[j]) ret++;
            count[i]--;
            
        }
        return ret;
        
    }
};

analysis

  • time complexity O(nlogn)
  • space complexity O(n)