2465. Number of Distinct Averages

發表於 | 分類於

problem

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int distinctAverages(vector<int>& nums) {
        
        // 0    1   3   4   4   5
        //  2.5 2.5 3.5
        
        sort(nums.begin(), nums.end() );
        unordered_set<float> ret;
        int n = nums.size(),  l = n/2;
        for(int i=0;i<l;++i)
        {
            float t = (nums[i] + nums[n-1-i]);
            ret.insert(t/2);
        }
        return ret.size();
    }
};

analysis

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