2022-05-23：给定一个数组arr，你可以随意挑选其中的数字， 但是你挑选的数中，任何两个数a和b，必须Math.abs(a - b) ＞ 1。 返回你最
原创2022-05-23：给定一个数组arr，你可以随意挑选其中的数字， 但是你挑选的数中，任何两个数a和b，必须Math.abs(a - b) ＞ 1。 返回你最
原创
2022-05-23：给定一个数组arr，你可以随意挑选其中的数字，
但是你挑选的数中，任何两个数a和b，必须Math.abs(a - b) > 1。
返回你最多能挑选几个数。
来自美团。
答案2022-05-23：
排序，去重。
第1种情况：不要i，dp[i]=dp[i-1]。
第2种情况：要i，
相邻差2，dp[i]=dp[i-1]+1。
相邻差1，dp[i]=dp[i-2]+1。
时间复杂度：排序的。
额外空间复杂度：O(N)。
代码用rust编写。代码如下：
```rust
use rand::Rng;
fn main() {
let mut len: i32 = 10;
let mut value: i32 = 20;
let mut test_time: i32 = 2000;
println!("测试开始");
for i in 0..test_time {
let n: i32 = rand::thread_rng().gen_range(0, len) + 1;
let mut arr = random_array(n, value);
let ans1 = longest_uncontinuous1(&mut arr);
let ans2 = longest_uncontinuous2(&mut arr);
if (ans1 != ans2) {
println!("出错了!");
for num in &arr {
print!("{} ", num);
}
println!("");
println!("ans1 = {}", ans1);
println!("ans2 = {}", ans2);
break;
}
}
println!("测试结束");
}
fn longest_uncontinuous1(arr: &mut Vec<i32>) -> i32 {
if arr.len() == 0 {
return 0;
}
arr.sort_unstable();
let mut pa: Vec<i32> = vec![];
for _i in 0..arr.len() {
pa.push(0);
}
return process1(arr, 0, &mut pa, 0);
}
fn process1(arr: &mut Vec<i32>, i: i32, path: &mut Vec<i32>, j: i32) -> i32 {
if i == arr.len() as i32 {
for k in 1..j {
if (path[(k - 1) as usize] + 1 >= path[k as usize]) {
return 0;
}
}
return j;
} else {
let mut p1 = process1(arr, i + 1, path, j);
path[j as usize] = arr[i as usize];
let mut p2 = process1(arr, i + 1, path, j + 1);
return get_max(p1, p2);
}
}
// 最优解
fn longest_uncontinuous2(arr: &mut Vec<i32>) -> i32 {
if arr.len() == 0 {
return 0;
}
arr.sort_unstable();
let n = arr.len() as i32;
let mut size: i32 = 1;
for i in 1..n {
if arr[i as usize] != arr[(size - 1) as usize] {
arr[size as usize] = arr[i as usize];
size += 1;
}
}
let mut dp: Vec<i32> = vec![];
dp.push(1);
let mut ans: i32 = 1;
for i in 1..size {
dp.push(1);
if arr[i as usize] - arr[(i - 1) as usize] > 1 {
dp[i as usize] = 1 + dp[(i - 1) as usize];
}
if i - 2 >= 0 && arr[i as usize] - arr[(i - 2) as usize] > 1 {
dp[i as usize] = get_max(dp[i as usize], 1 + dp[(i - 2) as usize]);
}
ans = get_max(ans, dp[i as usize]);
}
return ans;
}
fn get_max(a: i32, b: i32) -> i32 {
if a > b {
a
} else {
b
}
}
// 为了测试
fn random_array(n: i32, v: i32) -> Vec<i32> {
let mut arr: Vec<i32> = vec![];
for _i in 0..n {
arr.push(rand::thread_rng().gen_range(0, v) - rand::thread_rng().gen_range(0, v));
}
return arr;
}
```
执行结果如下：
***
[左神java代码](https://github.com/algorithmzuo/weekly-problems/blob/main/src/class_2022_03_3_week/Code01_LongestUncontinuousSet.java)
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。