1608 特殊数组的特征值——Leetcode 天天刷（2022.9.12）【排序】
前言
刚做了今天的每日一题，不愧是绿色，题目确实很绿色，可以直接暴力，但是用下排序会快上不少，有不少大佬用上了二分优化，但是个人觉得没太大必要。
题目描述
有兴趣的可以试试。
就是给定一个数组，数字都是非负整数。判断是否存在一个数字 x，如果数组中有 x 个整数不小于 x，则 x 就是该数组的 特征值，返回特征值，如果不存在，则返回 -1。
本地输入输出
输入
多组输入，每组的第一行输入一个整数n，第二行输入n个整数。
输出
每组输出单行，每行一个数字，表示特征值。
输入示例
2
3 5
2
0 0
5
0 4 3 0 4
5
3 6 7 7 0
输出示例
2
-1
3
-1
数据范围
1 <= nums.length <= 1000 <= nums[i] <= 1000
题解——排序
我们可以将数组先进行升序排序，从数组的尺寸开始向下判断，我们记枚举的数字是num，num 首先需要比数组当前值小于等于，如果当前不是数组的首位，就需要与前一个值比较，num需要大于下一个值。
这里由于数组尺寸一定大于0，所以答案一定不会是0。
算法分析
时间复杂度： O ( log ? n ) O(\log n) O(logn)， 主要来自排序。
空间复杂度：
O
(
log
?
n
)
O(\log n)
O(logn)， 还是在排序，使用排序函数存在 **归并排序**时会使用额外的空间。
Code（C++）
#include<bits/stdc++.h>
using namespace std;
class Solution
{
public:
// 排序+单次遍历
// 将数组按升序排序后，从数组的元素数量大小开始向下判断
// 选定的数值num从n，就是数组尺寸开始，每次数组指针向后移动都需要-1
// num首先需要比数组当前值小或者等，若当前值不为数组首位，则还需要与前一个值大
// 否则向后移动
int specialArray(vector<int>& nums)
{
sort(nums.begin(), nums.end()); // 排序，结果为升序
int n = nums.size();
int ans = -1; // 初始化为-1
int num = n;
// 遍历数组
for(int i = 0; i < n && num; ++i, --num)
{
// 答案条件
if((num <= nums[i]) && (!i || (i && num > nums[i - 1])))
{
ans = num;
break;
}
}
return ans;
}
};
int main()
{
int n;
Solution* sol = new Solution();
while(scanf("%d", &n))
{
vector<int> nums(n);
for(int i = 0; i < n; ++i)
{
scanf("%d", &nums[i]);
}
printf("%d\n", sol->specialArray(nums));
}
delete sol;
return 0;
}
后话
要准备国赛了，后面有时间再更新最近打的一些周赛的题目。