1491. Average Salary Excluding the Minimum and Maximum Salary

發表於 | 分類於

problem

solution

option 1 - sort

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    double average(vector<int>& salary) {
        // sorting
        sort(salary.begin(), salary.end());
        double total = 0, n=salary.size();
        for(int i=1;i<n-1;++i) total+=salary[i];
        return total/(n-2);
        
    }
};

option 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    double average(vector<int>& salary) {
        
        double total = 0, n=salary.size();
        int mx = salary[0], mn = salary[1];
        for(int s:salary){
            total+=s;
            mx = max(mx,s);
            mn = min(mn, s);
        }
        total-= (mn+mx);
        return total/(n-2);
    }
};

analysis

  • option 1
    • time complexity O(nlogn)
  • option 2
    • time complexity O(n)