2022-08-06：给定一个数组arr，长度为N，arr中所有的值都在1~K范围上， 你可以删除数字

2022-08-06：给定一个数组arr，长度为N，arr中所有的值都在1~K范围上，
你可以删除数字，目的是让arr的最长递增子序列长度小于K。
返回至少删除几个数字能达到目的。
N <= 10^4，K <= 10^2。
来自京东。4.2笔试。

答案2022-08-06：

动态规划。
时间复杂度：O(NK)。
额外空间复杂度：O(NK)。
rust和typescript的代码都有。

代码用rust编写。代码如下：

use rand::Rng;
fn main() {
    let nn: i32 = 15;
    let kk: i32 = 6;
    let test_time: i32 = 10000;
    println!("测试开始");
    for _ in 0..test_time {
        let len = rand::thread_rng().gen_range(0, nn) + 1;
        let k = rand::thread_rng().gen_range(0, kk) + 1;
        let mut arr = random_array(len, k);
        let ans1 = min_remove1(&mut arr, k);
        let ans2 = min_remove2(&mut arr, k);
        if ans1 != ans2 {
            println!("ans1 = {:?}", ans1);
            println!("ans2 = {:?}", ans2);
            println!("出错了!");
            break;
        }
    }
    println!("测试结束");
}

// 暴力方法
// 为了验证
fn min_remove1(arr: &mut Vec<i32>, k: i32) -> i32 {
    let mut path0: Vec<i32> = vec![];
    for _ in 0..arr.len() {
        path0.push(0);
    }
    return process1(arr, 0, &mut path0, 0, k);
}

const MAX_VALUE: i32 = 2 << 31 - 1;

fn process1(arr: &mut Vec<i32>, index: i32, path0: &mut Vec<i32>, size: i32, k: i32) -> i32 {
    if index == arr.len() as i32 {
        return if length_of_lis(path0, size) < k {
            arr.len() as i32 - size
        } else {
            MAX_VALUE
        };
    } else {
        let p1 = process1(arr, index + 1, path0, size, k);
        path0[size as usize] = arr[index as usize];
        let p2 = process1(arr, index + 1, path0, size + 1, k);
        return get_min(p1, p2);
    }
}

fn get_min<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
    if a < b {
        a
    } else {
        b
    }
}

fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
    if a > b {
        a
    } else {
        b
    }
}

fn length_of_lis(arr: &mut Vec<i32>, size: i32) -> i32 {
    if size == 0 {
        return 0;
    }
    let mut ends: Vec<i32> = vec![];
    for _ in 0..size {
        ends.push(0);
    }
    ends[0] = arr[0];
    let mut right: i32 = 0;
    let mut l;
    let mut r;
    let mut m;
    let mut max = 1;
    for i in 1..size {
        l = 0;
        r = right;
        while l <= r {
            m = (l + r) / 2;
            if arr[i as usize] > ends[m as usize] {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        right = get_max(right, l);
        ends[l as usize] = arr[i as usize];
        max = get_max(max, l + 1);
    }
    return max;
}

// arr[0...index-1]上，选择了一些数字，之前的决定！
// len长度了！len = 3 ： 1 2 3
// arr[index....]是能够决定的，之前的，已经不能再决定了
// 返回：让最终保留的数字，凑不足k长度的情况下，至少要删几个！
fn zuo(arr: &mut Vec<i32>, index: i32, len: i32, k: i32) -> i32 {
    if len == k {
        return MAX_VALUE;
    }
    // 凑的(1...len)还不到(1...k)
    if index == arr.len() as i32 {
        return 0;
    }
    // 没凑到 < k, 有数字!
    let cur = arr[index as usize];
    // 可能性1：保留
    // 可能性2：删除
    // 1...3 3
    if len >= cur || len + 1 < cur {
        return zuo(arr, index + 1, len, k);
    }
    // 1..3  4
    // len + 1  == cur
    // 可能性1：保留
    let p1 = zuo(arr, index + 1, len + 1, k);
    // 可能性2：删除
    let mut p2 = MAX_VALUE;
    let next2 = zuo(arr, index + 1, len, k);
    if next2 != MAX_VALUE {
        p2 = 1 + next2;
    }
    return get_min(p1, p2);
}

// 正式方法
// 时间复杂度O(N*K)
fn min_remove2(arr: &mut Vec<i32>, k: i32) -> i32 {
    let n = arr.len() as i32;
    let mut dp: Vec<Vec<i32>> = vec![];
    for i in 0..n {
        dp.push(vec![]);
        for _ in 0..k {
            dp[i as usize].push(0);
        }
    }
    for i in 0..n {
        for j in 0..k {
            dp[i as usize][j as usize] = -1;
        }
    }
    return process2(arr, k, 0, 0, &mut dp);
}

fn process2(arr: &mut Vec<i32>, k: i32, index: i32, range: i32, dp: &mut Vec<Vec<i32>>) -> i32 {
    if range == k {
        return MAX_VALUE;
    }
    if index == arr.len() as i32 {
        return 0;
    }
    if dp[index as usize][range as usize] != -1 {
        return dp[index as usize][range as usize];
    }
    let mut ans: i32;
    if arr[index as usize] == range + 1 {
        let mut p1 = process2(arr, k, index + 1, range, dp);
        p1 += if p1 != MAX_VALUE { 1 } else { 0 };
        let p2 = process2(arr, k, index + 1, range + 1, dp);
        ans = get_min(p1, p2);
    } else {
        ans = process2(arr, k, index + 1, range, dp);
    }
    dp[index as usize][range as usize] = ans;
    return ans;
}

// 为了测试
fn random_array(len: i32, k: i32) -> Vec<i32> {
    let mut arr: Vec<i32> = vec![];
    for _ in 0..len {
        arr.push(rand::thread_rng().gen_range(0, k) + 1);
    }
    return arr;
}

执行结果如下：

代码用typescript编写。代码如下：

// 暴力方法
// 为了验证
function minRemove1(arr: number[], k: number): number {
  return process1(arr, 0, new Array(arr.length), 0, k);
}

var MAX_VALUE: number = 2147483647;
function process1(
  arr: number[],
  index: number,
  path: number[],
  size: number,
  k: number
): number {
  if (index == arr.length) {
    return lengthOfLIS(path, size) < k ? arr.length - size : MAX_VALUE;
  } else {
    var p1: number = process1(arr, index + 1, path, size, k);
    path[size] = arr[index];
    var p2: number = process1(arr, index + 1, path, size + 1, k);
    return Math.min(p1, p2);
  }
}

function lengthOfLIS(arr: number[], size: number): number {
  if (size == 0) {
    return 0;
  }
  var ends: number[] = new Array(size);

  ends[0] = arr[0];
  var right: number = 0;
  var l: number = 0;
  var r: number = 0;
  var m: number = 0;
  var max: number = 1;
  for (var i: number = 1; i < size; i++) {
    l = 0;
    r = right;
    while (l <= r) {
      m = Math.floor((l + r) / 2);
      if (arr[i] > ends[m]) {
        l = m + 1;
      } else {
        r = m - 1;
      }
    }
    right = Math.max(right, l);
    ends[l] = arr[i];
    max = Math.max(max, l + 1);
  }
  return max;
}

// arr[0...index-1]上，选择了一些数字，之前的决定！
// len长度了！len = 3 ： 1 2 3
// arr[index....]是能够决定的，之前的，已经不能再决定了
// 返回：让最终保留的数字，凑不足k长度的情况下，至少要删几个！
function zuo(arr: number[], index: number, len: number, k: number): number {
  if (len == k) {
    return MAX_VALUE;
  }
  // 凑的(1...len)还不到(1...k)
  if (index == arr.length) {
    return 0;
  }
  // 没凑到 < k, 有数字!
  var cur: number = arr[index];
  // 可能性1：保留
  // 可能性2：删除
  // 1...3 3
  if (len >= cur || len + 1 < cur) {
    return zuo(arr, index + 1, len, k);
  }
  // 1..3  4
  // len + 1  == cur
  // 可能性1：保留
  var p1: number = zuo(arr, index + 1, len + 1, k);
  // 可能性2：删除
  var p2: number = MAX_VALUE;
  var next2: number = zuo(arr, index + 1, len, k);
  if (next2 != MAX_VALUE) {
    p2 = 1 + next2;
  }
  return Math.min(p1, p2);
}

// 正式方法
// 时间复杂度O(N*K)
function minRemove2(arr: number[], k: number): number {
  var n: number = arr.length;
  var dp: number[][] = new Array(n);
  for (var i: number = 0; i < n; i++) {
    dp[i] = new Array(k);
  }
  for (var i: number = 0; i < n; i++) {
    for (var j: number = 0; j < k; j++) {
      dp[i][j] = -1;
    }
  }
  return process2(arr, k, 0, 0, dp);
}

function process2(
  arr: number[],
  k: number,
  index: number,
  range: number,
  dp: number[][]
): number {
  if (range == k) {
    return MAX_VALUE;
  }
  if (index == arr.length) {
    return 0;
  }
  if (dp[index][range] != -1) {
    return dp[index][range];
  }
  var ans: number = 0;
  if (arr[index] == range + 1) {
    var p1: number = process2(arr, k, index + 1, range, dp);
    p1 += p1 != MAX_VALUE ? 1 : 0;
    var p2: number = process2(arr, k, index + 1, range + 1, dp);
    ans = Math.min(p1, p2);
  } else {
    ans = process2(arr, k, index + 1, range, dp);
  }
  dp[index][range] = ans;
  return ans;
}

// 为了验证
function randomArray(len: number, k: number): number[] {
  var arr: number[] = new Array(len);
  for (var i: number = 0; i < len; i++) {
    arr[i] = Math.floor(Math.random() * k) + 1;
  }
  return arr;
}

// 为了验证
function main() {
  var N: number = 15;
  var K: number = 6;
  var testTime: number = 10000;
  console.log("测试开始");
  for (var i: number = 0; i < testTime; i++) {
    var len: number = Math.floor(Math.random() * N) + 1;
    var k: number = Math.floor(Math.random() * K) + 1;
    var arr: number[] = randomArray(len, k);
    var ans1: number = minRemove1(arr, k);
    var ans2: number = minRemove2(arr, k);
    if (ans1 != ans2) {
      console.log("出错了！");
      arr.forEach(function (num) {
        console.log(num + " ");
      });

      console.log();
      console.log("k : " + k);
      console.log("ans1 : " + ans1);
      console.log("ans2 : " + ans2);
      break;
    }
  }
  console.log("测试结束");
}

main();

执行结果如下：

左神java代码

本作品采用《CC 协议》，转载必须注明作者和本文链接