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编写。代码如下：

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代码

2022-05-23：给定一个数组arr，你可以随意挑选其中的数字， 但是你挑选的数中，任何两个数a和b，必须Math.abs(a - b) ＞ 1。 返回你最多能挑选几个数。 来自美团。的相关教程结束。