Java C++ 算法题解leetcode1608特殊数组特征值
作者:AnjaVon 时间:2023-05-21 21:09:01
题目要求
思路一:枚举 + 二分
逐一枚举值域内的所有值,然后二分判断是否合法。
Java
class Solution {
public int specialArray(int[] nums) {
Arrays.sort(nums);
int n = nums.length;
for (int x = 0; x <= nums[n - 1]; x++) { // 枚举
int l = 0, r = n -1 ;
while (l < r) { // 二分
int m = l + r >> 1;
if (nums[m] >= x)
r = m;
else
l = m + 1;
}
if (nums[r] >= x && x == n - r)
return x;
}
return -1;
}
}
时间复杂度:O(n log n),排序复杂度为O(n log n),枚举次数为值域范围C=1000,所以找答案的复杂度为O(C log n)
空间复杂度:O(log n))
C++
class Solution {
public:
int specialArray(vector<int>& nums) {
sort(nums.begin(), nums.end());
int n = nums.size();
for (int x = 0; x <= nums[n - 1]; x++) { // 枚举
int l = 0, r = n -1 ;
while (l < r) { // 二分
int m = (l + r) >> 1;
if (nums[m] >= x)
r = m;
else
l = m + 1;
}
if (nums[r] >= x && x == n - r)
return x;
}
return -1;
}
};
时间复杂度:O(n log n),排序复杂度为O(n log n),枚举次数为值域范围C=1000,所以找答案的复杂度为O(C log n)
空间复杂度:O(log n)
思路二:二分枚举
二分枚举+二分判定是否合法;
为了方便把判断合法单独写成函数getResgetResgetRes。
Java
class Solution {
int[] nums;
public int specialArray(int[] num) {
this.nums = num;
Arrays.sort(nums);
int l = 0, r = nums[nums.length - 1];
while (l < r) {
int m = l + r >> 1;
if (getRes(m) <= m)
r = m;
else
l = m + 1;
}
return getRes(r) == r ? r : -1;
}
int getRes(int x) {
int n = nums.length, l = 0, r = n - 1;
while (l < r) {
int m = l + r >> 1;
if (nums[m] >= x)
r = m;
else
l = m + 1;
}
return nums[r] >= x ? n - r : 0;
}
}
时间复杂度:O(n log n),排序复杂度为O(n log n),二分找答案所以复杂度为O(log C log n)
空间复杂度:O(log n)
C++
注意全局变量和输入变量需要有差别……
class Solution {
public:
vector<int> nums;
int specialArray(vector<int>& num) {
this->nums = num;
sort(nums.begin(), nums.end());
int l = 0, r = nums[nums.size() - 1];
while (l < r) {
int m = (l + r) >> 1;
if (getRes(m) <= m)
r = m;
else
l = m + 1;
}
return getRes(r) == r ? r : -1;
}
int getRes(int x) {
int n = nums.size(), l = 0, r = n - 1;
while (l < r) {
int m = (l + r) >> 1;
if (nums[m] >= x)
r = m;
else
l = m + 1;
}
return nums[r] >= x ? n - r : 0;
}
};
时间复杂度:O(n log n),排序复杂度为O(n log n),二分找答案所以复杂度为O(log C log n)
空间复杂度:O(log n)
思路三:倒序枚举
因为值域比较小,所以可以直接从值域最后开始倒着枚举;
预处理出每个值出现的次数,然后记录当前合法合法数值的数量与当前数值进行比较。
Java
class Solution {
public int specialArray(int[] nums) {
int[] cnt = new int[1001];
for (int x : nums)
cnt[x]++;
for (int i = 1000, tot = 0; i >= 0; i--) {
tot += cnt[i]; // 数量
if (i == tot)
return i;
}
return -1;
}
}
时间复杂度:O(n+C)
空间复杂度:O(C)
C++
class Solution {
public:
int specialArray(vector<int>& nums) {
int cnt[1001];
memset(cnt, 0, sizeof(cnt));
for (int x : nums)
cnt[x]++;
for (int i = 1000, tot = 0; i >= 0; i--) {
tot += cnt[i];
if (i == tot)
return i;
}
return -1;
}
};
时间复杂度:O(n+C)
空间复杂度:O(C)
来源:https://juejin.cn/post/7142521741795917854
标签:Java,C++,算法,特殊数组,特征值
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
详解Java之冒泡排序与选择排序
2021-11-06 12:49:24
![](https://img.aspxhome.com/file/2023/7/122327_0s.jpg)
Java如何使用HTTPclient访问url获得数据
2023-11-12 04:16:21
Unity3D UGUI实现翻书特效
2022-03-30 23:02:59
![](https://img.aspxhome.com/file/2023/0/82120_0s.jpg)
Android 中糟糕的AsyncTask
2022-07-09 00:43:35
Java线程的全方位详解
2023-04-11 14:02:55
![](https://img.aspxhome.com/file/2023/2/61042_0s.png)
java中Vector类的常用方法详解
2023-11-26 10:29:07
![](https://img.aspxhome.com/file/2023/4/60234_0s.png)
C# 7.0中解构功能详解
2022-08-11 21:06:34
![](https://img.aspxhome.com/file/2023/2/88352_0s.png)
C#字符串内存分配与驻留池学习分享
2022-07-02 12:11:29
Java实现二分搜索树的示例代码
2023-08-05 10:43:40
![](https://img.aspxhome.com/file/2023/5/62145_0s.png)
Java获取任意http网页源代码的方法
2022-07-06 01:45:37
MyBatis查询结果resultType返回值类型的说明
2021-10-25 21:37:39
![](https://img.aspxhome.com/file/2023/9/79169_0s.jpg)
wenserver获取天气预报数据实例分享
2021-07-22 14:22:52
Android中bindService基本使用方法概述
2023-08-05 19:18:56
![](https://img.aspxhome.com/file/2023/6/85446_0s.png)
详解关于Android Studio中安装和gradle的一些坑
2023-06-10 05:58:30
![](https://img.aspxhome.com/file/2023/8/120048_0s.png)
Java 八种基本类型和基本类型封装类
2023-11-26 14:15:16
![](https://img.aspxhome.com/file/2023/8/59898_0s.jpg)
Java中线程的等待与唤醒_动力节点Java学院整理
2023-07-17 04:03:05
![](https://img.aspxhome.com/file/2023/4/57694_0s.png)
详解OAuth2 Token 一定要放在请求头中吗
2022-05-01 09:43:15
![](https://img.aspxhome.com/file/2023/3/76543_0s.jpg)
C#中实现可变参数实例
2022-03-27 15:48:07
Java实现上传文件图片到指定服务器目录
2023-06-28 00:23:32
深入浅出重构Mybatis与Spring集成的SqlSessionFactoryBean(上)
2021-12-01 18:27:49
![](https://img.aspxhome.com/file/2023/5/62085_0s.png)