🔗 🟢 3194. Minimum Average of Smallest and Largest Elements 1195

tags: Weekly Contest 403 陣列(Array) 排序(Sorting) 雙指標(Two Pointers)

題意

你有一個最初為空的浮點數陣列 averagesaverages。

你將得到一個包含 nn 個整數的陣列 numsnums，其中 nn 是偶數。

你需要重複以下過程 n2\frac{n}{2} 次：

  • 從 numsnums 中移除最小元素 minElementminElement 和最大元素 maxElementmaxElement。
  • 將 minElement+maxElement2\frac{minElement + maxElement}{2} 添加到 averagesaverages。

返回 averagesaverages 中的 最小 元素。

思路

方法一：排序(Sorting) + 雙指標(Two Pointers)

由於我們在每次操作中只會移除 numsnums 中最小和最大元素，且操作後的元素不會重新被加入到陣列 numsnums 中，因此我們可以先對陣列進行 排序(Sorting) ，然後使用 雙指標(Two Pointers) 來同時選取當前的最小和最大元素，令 leftleft 指向當前最小元素、 rightright 指向當前最大元素，計算它們的平均值並更新最小的平均值。

複雜度分析

  • 時間複雜度：O(nlog⁡n)\mathcal{O}(n \log n)。
    • 排序的時間複雜度為 O(nlog⁡n)\mathcal{O}(n \log n)
    • 雙指標遍歷的時間複雜度為 O(n)\mathcal{O}(n)
  • 空間複雜度：O(n)\mathcal{O}(n) 或 O(log⁡n)\mathcal{O}(\log n)，取決於排序演算法所需的空間複雜度。
    • 在 Python 中，sort() 是基於 Timsort 的，其空間複雜度為 O(n)\mathcal{O}(n)
    • 而在 C++ 中，sort() 是 QuickSort、HeapSort 和 Insertion Sort 的混合實現，其空間複雜度為 O(log⁡n)\mathcal{O}(\log n)。
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def minimumAverage(self, nums: List[int]) -> float:
        n = len(nums)
        nums.sort()
        ans = float("inf")
        left, right = 0, n - 1
        while left < right:
            ans = min(ans, (nums[left] + nums[right]) / 2)
            left += 1
            right -= 1
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    double minimumAverage(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        double ans = FLT_MAX;
        int left = 0, right = n - 1;
        while (left < right) {
            ans = min(ans, (nums[left++] + nums[right--]) / 2.0);
        }
        return ans;
    }
};

方法二：方法一優化

注意到在方法一中兩個指標是同步向中心移動的，也就是說 right=n−1−leftright = n - 1 - left，因此我們可以將雙指標的遍歷過程優化為單指標的遍歷過程。

此外，我們在每次更新最小值時，都需要進行一次浮點數除法，總共需要計算 n2\frac{n}{2} 次，這樣會導致時間增加。因此，我們可以在最後一次性計算平均值就好。

雖然時間複雜度和空間複雜度都沒有變化，但是實際上節省了 n2−1\frac{n}{2} - 1 次浮點數除法的時間，在本題中有巨大的效能提升。

複雜度分析

  • 時間複雜度：O(nlog⁡n)\mathcal{O}(n \log n)。
  • 空間複雜度：O(n)\mathcal{O}(n) 或 O(log⁡n)\mathcal{O}(\log n)。
1
2
3
4
5
class Solution:
    def minimumAverage(self, nums: List[int]) -> float:
        n = len(nums)
        nums.sort()
        return min(nums[i] + nums[n - 1 - i] for i in range(n // 2)) / 2
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    double minimumAverage(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        int ans = nums[0] + nums[n - 1];
        for (int i = 1; i < n / 2; i++) {
            ans = min(ans, nums[i] + nums[n - 1 - i]);
        }
        return ans / 2.0;
    }
};

寫在最後

PROMPT

masterpiece, best quality, high quality, extremely detailed CG unity 8k wallpaper, extremely detailed, High Detail, vibrant colors, backlight, photo background,

(1girl, solo), long hair, (black eyes), looking at viewer, (standing), full body, black hair, school uniform, short sleeves, pleated skirt, skirt, shirt, (green top, green shirt), black bottom, (black skirt), serafuku, socks, looking back, indoors, sailor collar, black footwear, window, white socks, hallway,

A girl in a green shirt and black pleated skirt standing, in a long school hallway, windows and doors on both sides, bright natural light coming through the windows, serene atmosphere, looking back at the camera,