1608-特殊数组的特征值

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:28 2023-09-13 16:06:28 Updated    

给你一个非负整数数组 nums 。如果存在一个数 x ，使得 nums 中恰好有 x 个元素 大于或者等于 x ，那么就称
nums 是一个 特殊数组 ，而 x 是该数组的 特征值 。

注意： x 不必 是 nums 的中的元素。

如果数组 nums 是一个 特殊数组 ，请返回它的特征值 x 。否则，返回 __-1 。可以证明的是，如果 nums
是特殊数组，那么其特征值 x 是 唯一的 。

示例 1：

**输入：** nums = [3,5]
**输出：** 2
**解释：** 有 2 个元素（3 和 5）大于或等于 2 。

示例 2：

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

示例 3：

**输入：** nums = [0,4,3,0,4]
**输出：** 3
**解释：** 有 3 个元素大于或等于 3 。

示例 4：

**输入：** nums = [3,6,7,7,0]
**输出：** -1

提示：

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

方法一：降序排序 + 一次遍历

思路与算法

我们可以首先将数组进行降序排序，这样一来，我们就可以通过遍历的方式得到数组的特征值了。

根据特征值 x 的定义，x 一定是在 [1, n] 范围内的一个整数，其中 n 是数组 nums 的长度。因此，我们可以遍历 [1, n] 并判断某个整数 i 是否为特征值。

若 i 为特征值，那么 nums 中恰好有 i 个元素大于等于 i。由于数组已经降序排序，说明 nums}[i-1] 必须大于等于 i，并且 nums}[i]（如果存在）必须小于 i。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int specialArray(vector<int>& nums) {
        sort(nums.begin(), nums.end(), greater<int>());
        int n = nums.size();
        for (int i = 1; i <= n; ++i) {
            if (nums[i - 1] >= i && (i == n || nums[i] < i)) {
                return i;
            }
        }
        return -1;
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int specialArray(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 0, j = n - 1; i < j; i++, j--) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
        for (int i = 1; i <= n; ++i) {
            if (nums[i - 1] >= i && (i == n || nums[i] < i)) {
                return i;
            }
        }
        return -1;
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public int SpecialArray(int[] nums) {
        Array.Sort(nums);
        int n = nums.Length;
        for (int i = 0, j = n - 1; i < j; i++, j--) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
        for (int i = 1; i <= n; ++i) {
            if (nums[i - 1] >= i && (i == n || nums[i] < i)) {
                return i;
            }
        }
        return -1;
    }
}
[sol1-Python3]
1
2
3
4
5
6
7
8
class Solution:
    def specialArray(self, nums: List[int]) -> int:
        nums.sort(reverse=True)
        n = len(nums)
        for i in range(1, n + 1):
            if nums[i - 1] >= i and (i == n or nums[i] < i):
                return i
        return -1
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
static inline int cmp(const void *pa, const void *pb) {
    return *(int *)pb - *(int *)pa;
}

int specialArray(int* nums, int numsSize) {
    qsort(nums, numsSize, sizeof(int), cmp);
    for (int i = 1; i <= numsSize; ++i) {
        if (nums[i - 1] >= i && (i == numsSize || nums[i] < i)) {
            return i;
        }
    }
    return -1;
}
[sol1-Golang]
1
2
3
4
5
6
7
8
9
func specialArray(nums []int) int {
    sort.Sort(sort.Reverse(sort.IntSlice(nums)))
    for i, n := 1, len(nums); i <= n; i++ {
        if nums[i-1] >= i && (i == n || nums[i] < i) {
            return i
        }
    }
    return -1
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var specialArray = function(nums) {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    for (let i = 0, j = n - 1; i < j; i++, j--) {
        const temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    for (let i = 1; i <= n; ++i) {
        if (nums[i - 1] >= i && (i === n || nums[i] < i)) {
            return i;
        }
    }
    return -1;
};

复杂度分析

  • 时间复杂度：O(n \log n)，其中 n 是数组 nums 的长度。

  • 空间复杂度：O(\log n)，即为排序需要的栈空间。

 Comments
On this page
1608-特殊数组的特征值