侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【排序, 双指针】不同的平均值数目【力扣第 91 场双周赛】

GabrielxD
2022-11-12 / 0 评论 / 0 点赞 / 12 阅读 / 505 字 / 正在检测是否收录...

题目

6237. 不同的平均值数目


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

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

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

两数 ab平均值(a + b) / 2

  • 比方说,23 的平均值是 (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

解题

方法一:哈希表 排序 双指针

思路

把数组排序,维护两个指针(ij)分别指向数组两端,双指针指向的值就分别是最大最小值,求出它们的平均值并放入哈希表(st)中去重,两个指针不断收缩就相当于不断删除最大最小值,最后哈希表的大小就是不同平均值的数目。

代码

class Solution {
    public int distinctAverages(int[] nums) {
        Set<Double> st = new HashSet<>();
        Arrays.sort(nums);
        for (int i = 0, j = nums.length - 1; i < j; ++i, --j) st.add((nums[i] + nums[j]) / 2.0);
        return st.size();
    }
}
0

评论区