1708 - 四数最小值

题目描述：

给定长度为 n 的整数序列，找出其中最小的四个数。如果有重复元素只算一次。

输入格式：

第一行包含整数 n。

第二行包含 n 个整数，表示整数序列。

输出格式：

共一行，包含四个整数，表示所有整数中最小的四个数，按从小到大的顺序排列。

数据范围：

1≤n≤105，

输入样例：

5
3 5 -1 7 8

输出样例：

-1 3 5 7

算法1

(排序) $O(nlogn)$

先将数组排序，然后输出前四个元素即可。

时间复杂度

排序的时间复杂度为 $O(nlogn)$，输出前四个元素的时间复杂度为 $O(1)$，所以总时间复杂度为 $O(nlogn)$。

C++ 代码

算法2

(堆) $O(nlog4)$

使用一个大小为4的小根堆，遍历数组，如果当前元素小于堆顶元素，则弹出堆顶元素，将当前元素加入堆中。最后输出堆中元素即可。

时间复杂度

遍历数组的时间复杂度为 $O(n)$，插入元素和弹出堆顶元素的时间复杂度均为 $O(log4)$，所以总时间复杂度为 $O(nlog4)$。

C++ 代码