2465. Number of Distinct Averages

  • Hardness: \(\color{green}\textsf{Easy}\)
  • Ralated Topics: Array、Hash Table、Two Pointers、Sorting
  • \(\color{blue}\textsf{Biweekly Contest 91}\)

一、題目

You are given a 0-indexed integer array nums of even length. As long as nums is not empty, you must repetitively:

  • Find the minimum number in nums and remove it.
  • Find the maximum number in nums and remove it.
  • Calculate the average of the two removed numbers. The average of two numbers a and b is (a + b) / 2.
  • For example, the average of 2 and 3 is (2 + 3) / 2 = 2.5. Return the number of distinct averages calculated using the above process. Note that when there is a tie for a minimum or maximum number, any can be removed.

Example 1:

  • Input: nums = [4,1,4,0,3,5]
  • Output: 2
  • Explanation:
  1. Remove 0 and 5, and the average is (0 + 5) / 2 = 2.5. Now, nums = [4,1,4,3].
  2. Remove 1 and 4. The average is (1 + 4) / 2 = 2.5, and nums = [4,3].
  3. Remove 3 and 4, and the average is (3 + 4) / 2 = 3.5.
    Since there are 2 distinct numbers among 2.5, 2.5, and 3.5, we return 2.

Example 2:

  • Input: nums = [1,100]
  • Output: 1
  • Explanation: There is only one average to be calculated after removing 1 and 100, so we return 1.

Constraints:

  • 2 <= nums.length <= 100
  • nums.length is even.
  • 0 <= nums[i] <= 100

二、分析

  • 每次取陣列中的最大值與最小值平均，再求有多少個相異的平均值。
  • 可以先用 sort 將陣列排序後，每次取頭尾做平均，再用 unordered_set 記錄。

三、解題

1. sort

  • Time complexity: \(O(n\log n)\)
  • Space complexity: \(O(n)\)
int distinctAverages(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    unordered_set<double> set;
    int n = nums.size();
    for (int i = 0; i < n/2; i++) {
        set.insert((nums[i] + nums[n-1-i])/2.0);
    }
    return set.size();
}

回目錄 Catalog