[LeetCode] 2465. Number of Distinct Averages

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