1608 特殊数组的特征值——Leetcode 天天刷（2022.9.12）【排序】

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
1
2
3
4
5
6
7
8
9
10
11
12
13

输出示例

2
-1
3
-1
1
2
3
4

数据范围

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 1000

题解——排序

我们可以将数组先进行升序排序，从数组的尺寸开始向下判断，我们记枚举的数字是num，num 首先需要比数组当前值小于等于，如果当前不是数组的首位，就需要与前一个值比较，num需要大于下一个值。

这里由于数组尺寸一定大于0，所以答案一定不会是0。

算法分析

时间复杂度：$O(\log n)$， 主要来自排序。

空间复杂度：$O(\log n)$， 还是在排序，使用排序函数存在 **归并排序**时会使用额外的空间。

Code（C++）

#include

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

后话

要准备国赛了，后面有时间再更新最近打的一些周赛的题目。