跳到主要内容

数组子序列

2024年03月14日
柏拉文
越努力，越幸运

一、最大整除子集​

给你一个由 无重复 正整数组成的集合 nums ，请你找出并返回其中最大的整除子集 answer ，子集中每一元素对 (answer[i], answer[j]) 都应当满足：

  • answer[i] % answer[j] == 0 ，或

  • answer[j] % answer[i] == 0 如果存在多个有效解子集，返回其中任何一个均可。

示例1:

输入：nums = [1,2,3]
输出：[1,2]
解释：[1,3] 也会被视为正确答案。

示例2:

输入：nums = [1,2,4,8]
输出：[1,2,4,8]

1.1 动态规划​

思路: 根据整除关系具有传递性，如果 a%c==0 b%c==0 , 那么 a%c ==0 ，解释了问题转移的特点，因此可以用动态规划求解

  1. 状态定义: dp[i] 表示在输入数组 nums 升序排列的前提下，以 nums[i] 为最大整数的整除子集的大小（在这种定义下 nums[i] 必须被选择）
  2. 状态转移方程: 枚举 j=0…i−1 的所有整数 nums[j]，如果 nums[j] 能整除 nums[i]，说明 nums[i] 可以扩充在以 nums[j] 为最大整数的整除子集里成为一个更大的整除子集。
    • 如果 nums[j] % nums[i] == 0 : dp[i]=dp[j]+1
    • 如果 nums[j] % nums[i] != 0 : dp[i]=dp[i]
    • 即得方程为: dp[i] = Math.max(dp[i], dp[j] + 1);
  3. 初始化: 由于 nums[i] 必须被选择，因此对于任意 i=0…n−1，初始的时候 dp[i]=1，这里 n 是输入数组的长度。
  4. 输出:
    • 倒序遍历数组 dp，直到找到 dp[i]=maxSize 为止，把此时对应的 nums[i] 加入结果集，此时 maxVal=nums[i]；
    • 然后将 maxSize 的值减 1，继续倒序遍历找到 dp[i]=maxSize，且 nums[i] 能整除 maxVal 的 i 为止，将此时的 nums[i] 加入结果集，maxVal 更新为此时的 num[i]；
    • 重复上述操作，直到 maxSize 的值变成 0，此时的结果集即为一个目标子集。
function largestDivisibleSubset(nums) {
    nums.sort((a,b)=>a-b);
    let dp=new Array(nums.length).fill(1);
    let maxSize=dp[0];
    let maxVal=nums[0];
    for(let i=1;i<nums.length;i++){ 
        for(let j=0;j<i;j++){
            if(nums[i]%nums[j]==0){
                dp[i]=Math.max(dp[i],dp[j]+1);
            }
        }
        if(dp[i]>maxSize){
            maxSize=dp[i];
            maxVal=nums[i];
        }
    }
    if(maxSize==1){
        return [nums[0]]
    }
    let result=new Array();
    for(let i=nums.length-1;i>=0&&maxSize>0;i--){
        if(dp[i]==maxSize&&maxVal%nums[i]==0){
            result.push(nums[i]);
            maxVal=nums[i];
            maxSize--;
        }
    }
    return result;
};

性能分析:

  • 时间复杂度：O(n^2)，其中 n 为输入数组的长度。
  • 空间复杂度：O(n)，其中 n 为输入数组的长度。需要创建长度为 n 的数组 dp。

二、最长等差数列​

给定一个整数数组 A，返回 A 中最长等差子序列的长度。

回想一下，A 的子序列是列表 A[i_1], A[i_2], ..., A[i_k] 其中 0 <= i_1 < i_2 < ... < i_k <= A.length - 1。并且如果 B[i+1] - B[i]( 0 <= i < B.length - 1) 的值都相同，那么序列 B 是等差的。

示例1:

输入：[3,6,9,12]
输出：4
解释： 
整个数组是公差为 3 的等差数列。

示例2:

输入：[9,4,7,2,10]
输出：3
解释：
最长的等差子序列是 [4,7,10]。

2.1 动态规划​

思路:

  1. 状态定义: dp[i][j]为以A[i]和A[j]为最后两个元素的等差数列的长度

    • 二维坐标转化为一维坐标: dp[i][j]=dp[i*len+j]

  2. 状态转移方程:

    • A[i]、A[j] 之前得一个元素target为: A[i]-(A[j]-A[i]) = 2*A[i]-A[j]

    • 可得状态方程: dp[i][j]=dp[map.get(target)][i]+1

    • 二维坐标转化为一维坐标: dp[i*len+j]=dp[map.get(target)*len+i]+1

    • 通过 map 记录 A[i] 元素 value-key

  3. 初始化状态: 因为等差数列最少元素数量是2，在i<j的时候初始化值为2

  4. 问题答案: dp 数组元素中的最大值

function longestArithSeqLength(nums) {
    const len=nums.length;
    const map=new Map();
    const dp=new Array(len*len).fill(2);
    let result=0;
    for(let i=0;i<len;i++){
        for(let j=i+1;j<len;j++){
            let target=2*nums[i]-nums[j];
            if(map.has(target)){
                dp[i*len+j]=dp[map.get(target)*len+i]+1;
            }
            result=Math.max(result,dp[i*len+j]);
        }
        map.set(nums[i],i);
    }
    return result;
};

三、最长递增子序列​

给你一个整数数组nums,找到其中最长严格递增子序列的长度。

示例1:

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例2:

输入：nums = [0,1,0,3,2,3]
输出：4

3.1 贪心+二分查找​

问题: 给你一个整数数组 nums, 找到其中最长严格递增子序列的长度。子序列 是由数组派生而来的序列,删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例1:

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例2:

输入：nums = [0,1,0,3,2,3]
输出：4

思路: 贪心+二分查找

  • 贪心思路: 如果我们要使上升子序列尽可能的长,则我们需要让序列上升得尽可能慢，因此我们希望每次在上升子序列最后加上的那个数尽可能的小

  • 初始化:

    • 维护一个数组 d[i]: 表示长度为 i 的最长上升子序列的末尾元素的最小值, d[1]=nums[0]

    • 用 len 记录目前最长上升子序列的长度: 起始时 len 为 1

  • 算法流程: 从前往后遍历数组 nums,在遍历到 nums[i] 时:

    • 如果 nums[i]>d[len], 则直接加入到 d 数组末尾，并更新 len=len+1

    • 否则，在 d 数组中二分查找(因为 d 数组是单调递增的，可以通过二分查找),找到第一个比 nums[i] 小的数 d[k]，并更新 d[k+1]=nums[i]

实现:

function binarySearch(left, right, target, array) {
  let l = left;
  let r = right;
  while (l < r) {
    let middle = (l + r) >> 1;
    if (array[middle] < target) {
      l = middle + 1;
    } else {
      r = middle;
    }
  }
  return l;
}

function lengthOfLIS(nums) {
  let len = 1;
  const dp = new Array(nums.length + 1);
  for (let i = 0; i < nums.length; i++) {
    const num = nums[i];
    if (num > dp[len]) {
      dp[++len] = num;
    } else {
      let pos = binarySearch(1, len, num, dp);
      dp[pos] = num;
    }
  }
  return len; // 返回递增序列长度 
  return dp.filter(i => i); // 返回递增序列
}

测试

const nums = [10, 9, 2, 5, 3, 7, 101, 18];
console.log(lengthOfLIS(nums));

  • 时间复杂度: O(nlogn)

  • 空间复杂度: O(n)

四、最长递增子序列的个数​

问题: 给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。

示例:

输入: [1,3,5,4,7]
输出: 2
解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。
输入: [2,2,2,2,2]
输出: 5
解释: 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5。

4.1 贪心 + 前缀和 + 二分查找​

  1. 我们将数组 d 扩展成一个二维数组，其中 d[i] 数组表示所有能成为长度为 i 的最长上升子序列的末尾元素的值。具体地，我们将更新 d[i]=nums[j] 这一操作替换成将 nums[j] 置于 d[i] 数组末尾。这样 d[i] 中就保留了历史信息，且 d[i] 中的元素是有序的（单调非增）。

  2. 类似地，我们也可以定义一个二维数组 cnt，其中 cnt[i][j] 记录了以 d[i][j] 为结尾的最长上升子序列的个数。为了计算 cnt[i][j]，我们可以考察 d[i−1] 和 cnt[i−1]，将所有满足 d[i−1][k]<d[i][j] 的 cnt[i−1][k] 累加到 cnt[i][j]，这样最终答案就是 cnt[maxLen] 的所有元素之和。

  3. 在代码实现时，由于 d[i]d[i]d[i] 中的元素是有序的，我们可以二分得到最小的满足 d[i−1][k]<d[i][j] 的下标 k。另一处优化是将 cnt 改为其前缀和，并在开头填上 0，此时 d[i][j] 对应的最长上升子序列的个数就是 cnt[i−1][−1]−cnt[i−1][k]，这里 [−1] 表示数组的最后一个元素。

function binarySearch1(left,right,target,array){
    let l = left;
    let r = right;
    while(l < r){
        const middle = (l + r) >> 1;
        const list = array[middle];
        if(list[list.length - 1] < target){
            l = middle + 1;
        }else{
            r = middle;
        }
    }
    return l;
}

function binarySearch2(left,right,target,array){
    let l = left;
    let r = right;
    while(l < r){
        const middle = (l + r) >> 1;
        if(array[middle] < target){
            r = middle;
        }else{
            l = middle + 1;
        }
    }
    return l;
}

function findNumberOfLIS(nums){
    const d = [];
    const cnt = [];
    for(const num of nums){
        const i = binarySearch1(0, d.length,num,d);
        let c = 1;
        if(i > 0){
            const k = binarySearch2(0,d[i-1].length,num,d[i-1]);
            c = cnt[i-1][cnt[i-1].length -1] - cnt[i-1][k];
        }
        if(i === d.length){
            const dList = [];
            dList.push(num);
            d.push(dList);
            const cntList = [];
            cntList.push(0);
            cntList.push(c);
            cnt.push(cntList);
        }else{
            d[i].push(num);
            const cntSize = cnt[i].length;
            cnt[i].push(cnt[i][cntSize - 1]+c);
        }
    }   

    const size1 = cnt.length;
    const size2 = cnt[size1 - 1].length;
    return cnt[size1 - 1][size2 -1];
}

复杂度分析

  • 时间复杂度: O(nlogn)

  • 空间复杂度: O(n)