Welcome to Subscribe On Youtube
2465. Number of Distinct Averages
Description
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
numsand remove it. - Find the maximum number in
numsand 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
2and3is(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 <= 100nums.lengthis even.0 <= nums[i] <= 100
Solutions
Solution 1: Sorting
The problem requires us to find the minimum and maximum values in the array $nums$ each time, delete them, and then calculate the average of the two deleted numbers. Therefore, we can first sort the array $nums$, then take the first and last elements of the array each time, calculate their sum, use a hash table or array $cnt$ to record the number of times each sum appears, and finally count the number of different sums.
The time complexity is $O(n \times \log n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the array $nums$.
-
class Solution { public int distinctAverages(int[] nums) { Arrays.sort(nums); Set<Integer> s = new HashSet<>(); int n = nums.length; for (int i = 0; i < n >> 1; ++i) { s.add(nums[i] + nums[n - i - 1]); } return s.size(); } } -
class Solution { public: int distinctAverages(vector<int>& nums) { sort(nums.begin(), nums.end()); unordered_set<int> s; int n = nums.size(); for (int i = 0; i < n >> 1; ++i) { s.insert(nums[i] + nums[n - i - 1]); } return s.size(); } }; -
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))) -
func distinctAverages(nums []int) (ans int) { sort.Ints(nums) n := len(nums) s := map[int]struct{}{} for i := 0; i < n>>1; i++ { s[nums[i]+nums[n-i-1]] = struct{}{} } return len(s) } -
function distinctAverages(nums: number[]): number { nums.sort((a, b) => a - b); const s: Set<number> = new Set(); const n = nums.length; for (let i = 0; i < n >> 1; ++i) { s.add(nums[i] + nums[n - i - 1]); } return s.size; } -
impl Solution { pub fn distinct_averages(nums: Vec<i32>) -> i32 { let mut nums = nums; nums.sort(); let n = nums.len(); let mut cnt = vec![0; 201]; let mut ans = 0; for i in 0..n >> 1 { let x = (nums[i] + nums[n - i - 1]) as usize; cnt[x] += 1; if cnt[x] == 1 { ans += 1; } } ans } }