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

解题思路

这道题的核心思路是模拟题目描述的过程，但可以通过排序优化。

方法一：排序 + 双指针

  • 将数组排序后，最小值在左端，最大值在右端
  • 使用双指针，左指针指向当前最小值，右指针指向当前最大值
  • 每次计算平均值并存储到集合中去重
  • 双指针向中间靠拢，直到相遇

方法二：直接模拟

  • 每次找到数组中的最小值和最大值并删除
  • 计算平均值并存储到集合中
  • 重复直到数组为空

排序方法的时间复杂度更优，推荐使用。

需要注意的是，为了避免浮点数精度问题，可以存储 (min + max) 而不是实际的平均值，因为两个不同的 (min + max) 对应不同的平均值。

代码实现

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

class Solution:
    def distinctAverages(self, nums: List[int]) -> int:
        nums.sort()
        sums = set()
        
        left, right = 0, len(nums) - 1
        while left < right:
            sums.add(nums[left] + nums[right])
            left += 1
            right -= 1
        
        return len(sums)

public class Solution {
    public int DistinctAverages(int[] nums) {
        Array.Sort(nums);
        HashSet<int> sums = new HashSet<int>();
        
        int left = 0, right = nums.Length - 1;
        while (left < right) {
            sums.Add(nums[left] + nums[right]);
            left++;
            right--;
        }
        
        return sums.Count;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var distinctAverages = function(nums) {
    nums.sort((a, b) => a - b);
    const sums = new Set();
    
    let left = 0, right = nums.length - 1;
    while (left < right) {
        sums.add(nums[left] + nums[right]);
        left++;
        right--;
    }
    
    return sums.size;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)排序需要 O(n log n)，双指针遍历需要 O(n)
空间复杂度O(n)集合最多存储 n/2 个不同的和值

相关题目