README.md

2465. 不同的平均值数目

English Version

题目描述

给你一个下标从 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

解法

方法一：排序 + 哈希表

我们先对数组进行排序，然后遍历数组，将 $nums[i]$ 与 $nums[n-i-1]$ 求和后放入哈希表中，最后返回哈希表的大小即可。

时间复杂度 $O(n\times \log n)$，空间复杂度 $O(n)$。其中 $n$ 为数组的长度。

Python3

class Solution:
    def distinctAverages(self, nums: List[int]) -> int:
        n = len(nums)
        nums.sort()
        return len(set(nums[i] + nums[n - i - 1] for i in range(n >> 1)))

Java

class Solution {
    public int distinctAverages(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        Set<Integer> s = new HashSet<>();
        for (int i = 0; i<n> > 1; ++i) {
            s.add(nums[i] + nums[n - i - 1]);
        }
        return s.size();
    }
}

C++

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

Go

func distinctAverages(nums []int) int {
	sort.Ints(nums)
	n := len(nums)
	s := map[int]struct{}{}
	for i := 0; i < n>>1; i++ {
		s[nums[i]+nums[n-i-1]] = struct{}{}
	}
	return len(s)
}

TypeScript

...