不同的平均值数目

标签: 数组哈希表双指针排序

难度: Easy

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

Submission

运行时间: 20 ms

内存: 16.0 MB

class Solution:
    def distinctAverages(self, nums: List[int]) -> int:
        nums.sort()
        ans = set()
        i = 0
        j = len(nums) - 1
        while i < j:
            ans.add((nums[i]+nums[j])/2)
            i += 1
            j -= 1
        return len(ans)

Explain

该题解思路是首先对数组进行排序，然后使用两个指针i和j分别指向数组的开始和结束位置。在每一次循环中，计算指针所指元素的平均值，并将此平均值存储在一个集合中，以确保平均值的唯一性。随后，将指针i向右移动，指针j向左移动，继续计算下一对元素的平均值。这个过程一直持续到i和j相遇或交错停止。最后，返回集合中元素的个数，即不同平均值的数量。

时间复杂度: O(n log n)

空间复杂度: O(n)

class Solution:
    def distinctAverages(self, nums: List[int]) -> int:
        # 对数组进行排序
        nums.sort()
        # 使用集合存储不同的平均值
        ans = set()
        # 初始化两个指针，分别指向数组的首尾
        i = 0
        j = len(nums) - 1
        # 当i小于j时，执行循环
        while i < j:
            # 计算i和j指向的两个元素的平均值，并加入集合
            ans.add((nums[i]+nums[j])/2)
            # 将i向右移动，j向左移动
            i += 1
            j -= 1
        # 返回集合中元素的数量，即不同平均值的数目
        return len(ans)

Explore

排序整个数组是为了保证使用双指针时，左指针i始终指向较小的元素，右指针j始终指向较大的元素，从而能够正确计算出所有可能的平均值。如果不进行排序，双指针遍历的组合可能会错过某些平均值，因为无序数组中较小和较大的元素不一定位于数组的两端。排序后的数组使得算法逻辑简单且易于保证覆盖所有不同的平均值。

在每次迭代中只移动i和j一步是为了确保不遗漏任何元素组合的平均值。虽然跳过重复的元素可能直接找到新的平均值，但这样做可能会错过一些重要的组合，特别是在数组中存在较多重复元素时。保持每次仅移动一步可以简化逻辑并确保算法的完整性。

如果数组中所有元素相同，如[2,2,2,2]，使用这种方法处理的结果将只能得到一个平均值，即2。因为所有元素相同，任何两个元素的平均值都是元素本身的值。这与预期一致，因为所有平均值事实上并无不同。

这个解法确实考虑到了数组长度为2的特殊情况。当数组只有两个元素时，双指针i和j分别指向这两个元素，计算它们的平均值后，指针就会相遇或交错，循环结束。这种情况下，算法有效地处理了仅存在的一对元素，返回的结果是1，表示只有一个不同的平均值。