How do I solve the Minimum Average of Smallest and Largest Elements problem?

Start by sorting the array, then use two pointers to pair the smallest and largest elements. Calculate the average for each pair and track the minimum average.

Why is sorting important for this problem?

Sorting ensures that the smallest and largest elements are paired optimally, making the calculation of averages more efficient and correct.

Can I solve this problem without sorting the array?

No, sorting is essential to optimally pair the smallest and largest elements for correct average calculation.

What is the time complexity of solving the Minimum Average of Smallest and Largest Elements?

The time complexity is O(n log n) due to the sorting step, where n is the length of the array.

What is the role of the two-pointer technique in this problem?

The two-pointer technique allows efficient pairing of the smallest and largest elements by scanning from both ends of the sorted array.

#3194

Easy

auto_awesome双·指针·invariant

LeetCode 题解工作台

最小元素和最大元素的最小平均值

你有一个初始为空的浮点数数组 averages 。另给你一个包含 n 个整数的数组 nums ，其中 n 为偶数。你需要重复以下步骤 n / 2 次：从 nums 中移除最小的元素 minElement 和最大的元素 maxElement 。将 (minElement + maxEle…

数组双指针排序

题目描述

你有一个初始为空的浮点数数组 averages。另给你一个包含 n 个整数的数组 nums，其中 n 为偶数。

你需要重复以下步骤 n / 2 次：

从 nums 中移除最小的元素 minElement 和最大的元素 maxElement。
将 (minElement + maxElement) / 2 加入到 averages 中。

返回 averages 中的最小元素。

示例 1：

输入： nums = [7,8,3,4,15,13,4,1]

输出： 5.5

解释：

步骤	nums	averages
0	[7,8,3,4,15,13,4,1]	[]
1	[7,8,3,4,13,4]	[8]
2	[7,8,4,4]	[8,8]
3	[7,4]	[8,8,6]
4	[]	[8,8,6,5.5]

返回 averages 中最小的元素，即 5.5。

示例 2：

输入： nums = [1,9,8,3,10,5]

输出： 5.5

解释：

步骤	nums	averages
0	[1,9,8,3,10,5]	[]
1	[9,8,3,5]	[5.5]
2	[8,5]	[5.5,6]
3	[]	[5.5,6,6.5]

示例 3：

输入： nums = [1,2,3,7,8,9]

输出： 5.0

解释：

步骤	nums	averages
0	[1,2,3,7,8,9]	[]
1	[2,3,7,8]	[5]
2	[3,7]	[5,5]
3	[]	[5,5,5]

提示：

2 <= n == nums.length <= 50
n 为偶数。
1 <= nums[i] <= 50

lightbulb

解题思路

方法一：排序

我们首先对数组 $\textit{nums}$ 进行排序，然后从数组的两端开始取元素，分别计算两个元素的和，取最小值。最后将最小值除以 2 作为答案返回即可。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(\log n)$ 。其中 $n$ 为数组 $\textit{nums}$ 的长度。

1

2

3

4

5

6

class Solution:
    def minimumAverage(self, nums: List[int]) -> float:
        nums.sort()
        n = len(nums)
        return min(nums[i] + nums[-i - 1] for i in range(n // 2)) / 2

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Tests the candidate's understanding of sorting and its role in pairing elements.
question_mark
Evaluates familiarity with two-pointer techniques and invariant tracking.
question_mark
Checks if the candidate can optimize average calculations by focusing on sorting and pairing.

warning

常见陷阱

外企场景

error
Failing to sort the array before pairing the elements.
error
Not properly updating the minimum average during the two-pointer scanning.
error
Ignoring edge cases, such as arrays with the smallest possible length.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Change the problem to return the maximum average instead of the minimum.
arrow_right_alt
Modify the problem to handle arrays of odd length.
arrow_right_alt
Adjust the problem to calculate the sum of all averages instead of the minimum.

help

常见问题

外企场景

继续练习

#3186 施咒的最大总伤害 #3132 找出与数组相加的整数 II #2824 统计和小于目标的下标对数目