无序数组及其子序列的相关问题研究

算法中以数组为研究对象的问题是非常常见的. 除了排序大家经常会遇到之外, 数组的子序列问题也是其中的一大分类. 今天我就对自己经常遇到的无序数组的子序列相关问题在这里总结一下.

 

前置条件: 给定无序数组. 以下所以的问题均以此为前置条件. 例如无序数组nums = [2, 1, 3].

 

问题1:

求子序列的个数. 例如前置无序数组的子序列个数为8, 分别为[], [2], [2, 1], [1], [2, 1, 3], [1, 3], [2, 3], [3].

分析: 

这个问题应该非常好理解. 对于它的子序列sub而言, 数组元素nums[i], 它要么存在于sub中, 要么不存在于sub中, 只有这两种可能. 所以, 元素nums[i]能构建的子序列个数为count(nums[i]) = 2. 因此, 对于数组nums的所有子序列的个数就为count(nums[0]) * count(nums[1]) * ... * count(nums[n-1]) = 2 * 2 * ... * 2 = 2^n(2的n次幂). 

所以, 对于长度为n的无序数组, 它的所有子序列的个数为 2^n.

 

问题2:

获取nums的所有子序列. 例如前置无序数组的所有子序列为[], [2], [2, 1], [1], [2, 1, 3], [1, 3], [2, 3], [3].

分析:

首先, 我们按照问题1的思路, "对于它的子序列sub而言, 数组元素nums[i], 它要么存在于sub中, 要么不存在于sub中, 只有这两种可能", 我们可以创建一个只包含了0和1的长度为n的数组, 则这个二进制数组可以表示的10进制数字的范围恰好为[0, 2^n - 1]. 这个思路可以用下面这个表格表示如下(利用前置条件中给定的数组nums):

binary ums	2	1	3	subsequences
0	0	0	0	[]
1	0	0	1	[3]
2	0	1	0	[1]
3	0	1	1	[1, 3]
...	...	...	...	...

所以, 我们可以遍历一下范围[0, 2^n - 1], 然后将10进制变量k转化为二进制数组, 然后利用二进制数组中1的个数和位置, 构建子序列.

这里提供一下上述思路的Java代码如下: 

public List> allSubsequences(int[] nums){
    if (nums == null){
        return null;
    }
    int max = Math.pow(2, nums.length);
    List> result = new ArrayList<>();
    for (int k = 0; k < max; k++){
        List sub = new ArrayList<>();
        String binary = Integer.toBinaryString(k);
        for(int i = binary.length() - 1; i >= 0; i--){
            if (binary.charAt(i) == '1'){
                sub.add(nums[nums.length - i - 1]);
            }
        }
        result.add(sub);
    }
    return result;
}

 

与此同时, 我们也可以利用动态规划的思想来解决这个问题.

对于元素nums[i], 我们将它的所有子序列表示为subs(i). 那么对于nums[i-1]和nums[i], 则存在这些一个关系:

subs(i) = [nums[i], (sub + nums[i])], 其中满足限制条件 sub in subs(i - 1). 

上述表达式想要表达的意思是: subs(i)生成的所有子序列, 由nums[i]和subs(i - 1)生成的所有子序列末尾加上nums[i]组成.

由此, 依据这种思路, 即利用动态规划思想生成所有子序列, 可以利用如下java代码实现:

public List> allSubsequences(int[] nums){
    if (nums == null){
        return null;
    }
    List> result = new ArrayList<>();
    result.add(new ArrayList<>());//add empty subsequence
    for(int num : nums){
        List> tmp = new ArrayList<>(result);
        for(List list : tmp){
            list.add(num);
        }
        result.addAll(tmp);
    }
    return result;
}

 

问题3:

求所有递增子序列的个数. 例如前置无序数组的递增子序列个数为5, 分别为[2], [1], [1, 3], [2, 3], [3].

分析: 

我们假设count(i)表示以nums[i]结尾的递增子序列个数. 则对于前置无序数组nums而言, 它的所有递增子序列的个数, 就是以nums[i]结尾的递增子序列的和, 表示为sum(count(i))(0 < i < n - 1).

理解了以上假设, 那么我们可以发现以下规律: 

count(0) = 1;

count(1) = 1; (nums[0] > nums[1])

count(2) = 1 + count(0) + count(1) (nums[0] < nums[2], nums[1] < nums[2])

             = 1 + 1 + 1 = 3;

所以, nums的所有递增子序列个数就是count = count(0) + count(1) + count(2) = 1 + 1 + 3 = 5;

因而, 我的思路是: 建立一个数组counts = new int[nums.length + 1]用于保存以nums[i]结尾的递增子序列的个数, 即counts[i] = count(i). 而counts[nums.length]则用于累积counts[i], 表示整个序列的递增子序列的个数.

上述思路的Java实现如下: 

public int countIncreasingSubsequences(int[] nums){
    if (nums == null){
        return -1;
    }
    int[] counts = new int[nums.length + 1];
    for(int i = 0; i < nums.length; i++){
        counts[i] = 1;//单元素递增序列计数
        for(int j = 0; j < i; j++){
            if(nums[i] > nums[j]){
                counts[i] += counts[j];
            }
        }
        counts[nums.length] += counts[i];
    }
    return counts[nums.length];
}

 

问题4:

求它的所有递增子序列. 例如前置无序数组的所有递增子序列为[2], [1], [1, 3], [2, 3], [3].

分析:

需要利用动态规划思想来分析这道题目. 其实, 大体思路跟求它的所有子序列相同, 只不过是本问题要求子序列是递增的, 所以, 就利用递增来修改求所有子序列的逻辑.

因而, 对于元素nums[i], 我们将它的所有子序列表示为subs(i). 那么对于nums[i-1]和nums[i], 则存在这些一个关系:

subs(i) = [nums[i], (sub + nums[i])], 其中满足限制条件 sub in subs(i - 1) & sub.lastElement < nums[i]. 

上述表达式想要表达的意思是: subs(i)生成的所有递增子序列, 由nums[i]和subs(i - 1)生成的所有末尾元素小于nums[i]的递增子序列末尾加上nums[i]组成.

由此, 依据这种思路, 即利用动态规划思想生成所有递增子序列, 可以利用如下java代码实现:

public List> allIncreasingSubsequences(int[] nums){
    if (nums == null){
        return null;
    }
    List> result = new ArrayList<>();
    for(int num : nums){
        List> tmp = new ArrayList<>();
        List firstList = new ArrayList<>();
        firstList.add(num);
        tmp.add(firstList);
        for(List list : result){
            if(list.get(list.size() - 1) < num){
                List newList = new ArrayList<>(list);
                newList.add(num);
                tmp.add(newList);
            }
        }
    }
    return result;
}

 

最后, 关于递减子序列的问题, 原理跟递增子序列问题是一样的, 这里就不再赘述, 有兴趣的同学, 可以自己手动写一下.