1608特殊数组的特征值（暴力、计数）

1. 问题描述&＃xff1a;

给你一个非负整数数组 nums 。如果存在一个数 x &＃xff0c;使得 nums 中恰好有 x 个元素 大于或者等于 x &＃xff0c;那么就称 nums 是一个 特殊数组 &＃xff0c;而 x 是该数组的 特征值 。
注意&＃xff1a; x 不必 是 nums 的中的元素。
如果数组 nums 是一个 特殊数组 &＃xff0c;请返回它的特征值 x 。否则&＃xff0c;返回 -1 。可以证明的是&＃xff0c;如果 nums 是特殊数组&＃xff0c;那么其特征值 x 是 唯一的 。

示例 1&＃xff1a;

输入&＃xff1a;nums &＃61; [3,5]
输出&＃xff1a;2
解释&＃xff1a;有 2 个元素&＃xff08;3 和 5&＃xff09;大于或等于 2 。

示例 2&＃xff1a;

输入&＃xff1a;nums &＃61; [0,0]
输出&＃xff1a;-1
解释&＃xff1a;没有满足题目要求的特殊数组&＃xff0c;故而也不存在特征值 x 。
如果 x &＃61; 0&＃xff0c;应该有 0 个元素 >&＃61; x&＃xff0c;但实际有 2 个。
如果 x &＃61; 1&＃xff0c;应该有 1 个元素 >&＃61; x&＃xff0c;但实际有 0 个。
如果 x &＃61; 2&＃xff0c;应该有 2 个元素 >&＃61; x&＃xff0c;但实际有 0 个。
x 不能取更大的值&＃xff0c;因为 nums 中只有两个元素。

示例 3&＃xff1a;

输入&＃xff1a;nums &＃61; [0,4,3,0,4]
输出&＃xff1a;3
解释&＃xff1a;有 3 个元素大于或等于 3 。

示例 4&＃xff1a;

输入&＃xff1a;nums &＃61; [3,6,7,7,0]
输出&＃xff1a;-1

2. 思路分析&＃xff1a;

① 首先特征值是小于等于数组长度的&＃xff0c;所以我们只需要在[0, len(nums)]的范围内尝试找出特征值&＃xff0c;对nums数组进行排序&＃xff0c;然后我们就可以使用循环计算出当前i小的元素的个数&＃xff0c;使用len(nums)减去计算出的元素个数那么得到的就为比当前i值大于等于的个元数&＃xff0c;比较i值与当前计算的个数是否相等&＃xff0c;如果相等那么当前的i就为特征值&＃xff08;其中i为[0, len(nums)]尝试的特征值&＃xff09;

② 另外一个方法可以使用列表来记录各个元素在对应位置出现的次数&＃xff0c;可以声明一个长度为len(nums) &＃43; 1的列表&＃xff0c;然后遍历nums数组&＃xff0c;对当前遍历到的元素对应的位置进行加1&＃xff0c;最后我们在for循环中倒序遍历计数列表&＃xff0c;计算出比当前的变量i大于等于的元素个数&＃xff0c;判断是否等于当前的循环变量&＃xff0c;如果相等那么当前的i就为特征值了

3. 代码如下&＃xff1a;

暴力&＃xff1a;

from typing import Listclass Solution:def specialArray(self, nums: List[int]) -> int:nums.sort()for i in range(1, len(nums) &＃43; 1):j, sum &＃61; 0, 0while j

计数&＃xff1a;

from typing import Listclass Solution:def specialArray(self, nums: List[int]) -> int:count &＃61; [0] * (len(nums) &＃43; 1)for i in nums:count[min(i, len(nums))] &＃43;&＃61; 1# 后面开始累加因为大于后面的数字肯定是大于前面的数字的n &＃61; 0for i in range(len(nums), -1, -1):n &＃43;&＃61; count[i]if n &＃61;&＃61; i: return ireturn -1