注意:时间复杂度:sort 排序为 O(n lon n),reverse为O(n),总复杂O(n lon n)
空间复杂度: 存储数组需要O(n)的额外空间
将序列按降序排序后,第 k 大的数即为下标 k-1 处的元素。
先输入n和k → 输入n个数 → 排序 → 反转 → 输出降序数组中下标为 k-1 的元素
有了思路代码也就显而易见了
这里为什么反转?
因为题目要求第 k大 的数,而 sort 默认升序,所以通过 reverse 得到降序序列,使第 k 大的数恰好位于下标 k-1 处。
这题最大限制10^6 int 类型足以存储题目给定的正整数
要小心的是
因为有最大10^6个数,所以不要用普通数组,最好用动态数组(例如vector),否则容易出现栈溢出的情况
还有,新手注意,普通数组没有 .begin() 成员函数。sort 的迭代器参数应使用 arr 和 arr+100,或 begin(arr), end(arr)。以下是错误示例:
注意:普通数组不能直接使用 .begin() 成员函数
还有如果你粗心写成了这样
大家也看出来了,vector没定义下标,所以这样直接赋值会越界
该怎么办呢?
如果你真的不想写小小的“(n)”那么可以这样
这样也可以达到相同的效果