给你一个下标从 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 <= 100nums.length 是偶数。0 <= nums[i] <= 100
方法一：排序 + 哈希表
思路与算法
我们对数组 nums 进行排序，随后使用两个指针，初始分别指向 nums 首元素和尾元素对数组进行遍历，就可以不断得到当前数组的最大值和最小值。
由于「不同平均值的数目」和「不同和的数目」是等价的，因此在计算时，可以直接求出两个指针指向元素的和，代替平均值，避免浮点运算。我们只需要使用一个哈希集合，将所有的和添加进去，随后哈希集合中的元素个数即为答案。
代码
[sol1-C++]1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public:
int distinctAverages(vector<int>& nums) {
sort(nums.begin(), nums.end());
unordered_set<int> seen;
for (int i = 0, j = nums.size() - 1; i < j; ++i, --j) {
seen.insert(nums[i] + nums[j]);
}
return seen.size();
}
};
|
[sol1-Python3]1
2
3
4
5
6
7
8
9
10
| class Solution:
def distinctAverages(self, nums: List[int]) -> int:
nums.sort()
seen = set()
i, j = 0, len(nums) - 1
while i < j:
seen.add(nums[i] + nums[j])
i += 1
j -= 1
return len(seen)
|
[sol1-Java]1
2
3
4
5
6
7
8
9
10
| class Solution {
public int distinctAverages(int[] nums) {
Arrays.sort(nums);
Set<Integer> seen = new HashSet<Integer>();
for (int i = 0, j = nums.length - 1; i < j; ++i, --j) {
seen.add(nums[i] + nums[j]);
}
return seen.size();
}
}
|
[sol1-C#]1
2
3
4
5
6
7
8
9
10
| public class Solution {
public int DistinctAverages(int[] nums) {
Array.Sort(nums);
ISet<int> seen = new HashSet<int>();
for (int i = 0, j = nums.Length - 1; i < j; ++i, --j) {
seen.Add(nums[i] + nums[j]);
}
return seen.Count;
}
}
|
[sol1-Go]1
2
3
4
5
6
7
8
| func distinctAverages(nums []int) int {
sort.Ints(nums)
seen := make(map[int]bool)
for i, j := 0, len(nums)-1; i < j; i, j = i + 1, j - 1 {
seen[nums[i] + nums[j]] = true
}
return len(seen)
}
|
[sol1-JavaScript]1
2
3
4
5
6
7
8
| var distinctAverages = function(nums) {
nums.sort((a, b) => a - b);
const seen = new Set();
for (let i = 0, j = nums.length - 1; i < j; i++, j--) {
seen.add(nums[i] + nums[j]);
}
return seen.size;
}
|
[sol1-C]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| int cmp(const void* a, const void* b) {
return *(int*)a - *(int*)b;
}
int distinctAverages(int* nums, int numsSize) {
qsort(nums, numsSize, sizeof(int), cmp);
int seen[201] = {};
int count = 0;
for (int i = 0, j = numsSize - 1; i < j; i++, j--) {
int sum = nums[i] + nums[j];
if (!seen[sum]) {
seen[sum] = 1;
count++;
}
}
return count;
}
|
复杂度分析
