LeetCode 2465. 不同的平均值数目-Toy模板网

这篇具有很好参考价值的文章主要介绍了LeetCode 2465. 不同的平均值数目。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

【LetMeFly】2465.不同的平均值数目

力扣题目链接：https://leetcode.cn/problems/number-of-distinct-averages/

给你一个下标从 0 开始长度为偶数的整数数组 nums 。

只要 nums 不是空数组，你就重复执行以下步骤：

找到 nums 中的最小值，并删除它。
找到 nums 中的最大值，并删除它。
计算删除两数的平均值。

两数 a 和 b 的 平均值 为 (a + b) / 2 。

比方说，2 和 3 的平均值是 (2 + 3) / 2 = 2.5 。

返回上述过程能得到的不同平均值的数目。

注意，如果最小值或者最大值有重复元素，可以删除任意一个。

示例 1：

输入：nums = [4,1,4,0,3,5]
输出：2
解释：
1. 删除 0 和 5 ，平均值是 (0 + 5) / 2 = 2.5 ，现在 nums = [4,1,4,3] 。
2. 删除 1 和 4 ，平均值是 (1 + 4) / 2 = 2.5 ，现在 nums = [4,3] 。
3. 删除 3 和 4 ，平均值是 (3 + 4) / 2 = 3.5 。
2.5 ，2.5 和 3.5 之中总共有 2 个不同的数，我们返回 2 。

示例 2：

输入：nums = [1,100]
输出：1
解释：
删除 1 和 100 后只有一个平均值，所以我们返回 1 。

提示：

2 <= nums.length <= 100
nums.length 是偶数。
0 <= nums[i] <= 100

方法一：排序 + 双指针 + 哈希

首先对原始数组排序，接着使用双指针分别指向数组的头和尾。

使用一个哈希表存放最大数和最小数之和（因为问的是不同的平均数的数量，因此没必要除以2）

最终返回哈希表中原始的个数即可。

时间复杂度 $O (l e n (n u m s))$
空间复杂度 $O (l e n (n u m s))$

AC代码

C++

class Solution {
public:
    int distinctAverages(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        unordered_set<int> se;
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            se.insert(nums[l++] + nums[r--]);
        }
        return se.size();
    }
};

Python

# from typing import List

class Solution:
    def distinctAverages(self, nums: List[int]) -> int:
        nums.sort()
        se = set()
        l, r = 0, len(nums) - 1
        while l < r:
            se.add(nums[l] + nums[r])
            l += 1
            r -= 1
        return len(se)