2022-05-23：给定一个数组arr，你可以随意挑选其中的数字， 但是你挑选的数中，任何两个数a和b

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