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

【LetMeFly】3194.最小元素和最大元素的最小平均值：排序

力扣题目链接：https://leetcode.cn/problems/minimum-average-of-smallest-and-largest-elements/

你有一个初始为空的浮点数数组 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

解题方法：排序

二话不说对原始数组排个序，使用$i$从$0$到$\frac{len(nums)}2-1$遍历，更新$nums[i]+nums[len(nums)-i-1]$的最小值。

遍历结束后，将最小值除以$2$并返回。

• 时间复杂度$O(n\log n)$
• 空间复杂度$O(\log n)$

AC代码

C++

class Solution {
public:
    double minimumAverage(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int ans = 1000;
        for (int i = 0; i < nums.size() / 2; i++) {
            ans = min(ans, nums[i] + nums[nums.size() - i - 1]);
        }
        return 1. * ans / 2;
    }
};

Go

package main
import "sort"

func minimumAverage(nums []int) float64 {
    sort.Ints(nums)
    ans := 1000
    for i := 0; i < len(nums) / 2; i++ {
        ans = min(ans, nums[i] + nums[len(nums) - i - 1])
    }
    return float64(ans) / 2
}

Java

import java.util.Arrays;

class Solution {
    public double minimumAverage(int[] nums) {
        Arrays.sort(nums);
        int ans = 1000;
        for (int i = 0; i < nums.length / 2; i++) {
            ans = Math.min(ans, nums[i] + nums[nums.length - i - 1]);
        }
        return 1. * ans / 2;
    }
}

Python

from typing import List

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

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

Tisfy：https://letmefly.blog.csdn.net/article/details/142994095