What is the main pattern for Number of Distinct Averages?

The main pattern is array scanning with two pointers after sorting and using a hash set to count distinct averages.

Can this method handle repeated numbers correctly?

Yes, the hash set ensures that repeated averages are only counted once, so duplicates do not affect the final count.

What is the optimal time complexity?

Sorting gives O(n log n) and scanning pairs gives O(n), so total time complexity is O(n log n).

How does integer division affect the result?

Use floating-point division to ensure averages are accurate; integer division may merge distinct averages incorrectly.

Is sorting always necessary for this problem?

Sorting simplifies pairing smallest and largest elements; without sorting, you need a more complex structure to track min and max efficiently.

#2465

Easy

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

不同的平均值数目

给你一个下标从 0 开始长度为偶数的整数数组 nums 。只要 nums 不是空数组，你就重复执行以下步骤：找到 nums 中的最小值，并删除它。找到 nums 中的最大值，并删除它。计算删除两数的平均值。两数 a 和 b 的平均值为 (a + b) / 2 。比方说， 2 和…

数组哈希表双指针排序

题目描述

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

lightbulb

解题思路

方法一：排序

题目中要求每次找到数组 $nums$ 中的最小值和最大值，然后删除它们，再计算删除两数的平均值。因此，我们可以先对数组 $nums$ 进行排序，然后每次取数组的首尾元素，计算它们的和，用哈希表或数组 $cnt$ 记录每个和出现的次数，最后统计不同的和的个数即可。

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

1

2

3

4

5

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

speed

复杂度分析

指标	值
时间	complexity is O(n log n) for sorting plus O(n) for scanning and averaging pairs. Space complexity is O(n) in the worst case for storing distinct averages in the hash set.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate quickly identifies the two-pointer pattern after sorting.
question_mark
Candidate suggests using a hash set to track distinct averages without recounting.
question_mark
Candidate properly handles edge cases where averages repeat multiple times.

warning

常见陷阱

外企场景

error
Failing to sort the array and mispairing elements.
error
Overwriting averages instead of storing in a set, losing distinct counts.
error
Incorrectly handling integer division versus floating-point averages.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Count distinct sums instead of averages for paired elements.
arrow_right_alt
Apply the method to odd-length arrays with one unpaired element ignored.
arrow_right_alt
Compute averages using a sliding window instead of pair removal.

help

常见问题

外企场景

继续练习

#2441 与对应负数同时存在的最大正整数 #2491 划分技能点相等的团队 #2122 还原原数组