算法中以数组为研究对象的问题是非常常见的. 除了排序大家经常会遇到之外, 数组的子序列问题也是其中的一大分类. 今天我就对自己经常遇到的无序数组的子序列相关问题在这里总结一下.
前置条件: 给定无序数组. 以下所以的问题均以此为前置条件. 例如无序数组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\nums 2 1 3 subsequences0 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<List<Integer>> allSubsequences(int[] nums){
if (nums == null){
return null;
}
int max = Math.pow(2, nums.length);
List<List<Integer>> result = new ArrayList<>();
for (int k = 0; k < max; k++){
List<Integer> 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<List<Integer>> allSubsequences(int[] nums){
if (nums == null){
return null;
}
List<List<Integer>> result = new ArrayList<>();
result.add(new ArrayList<>());//add empty subsequence
for(int num : nums){
List<List<Integer>> tmp = new ArrayList<>(result);
for(List<Integer> list : tmp){
list.add(num);
}
result.addAll(tmp);
}
return result;
}
问题3:
求所有递增子序列的个数. 例如前置无序数组的递增子序列个数为5, 分别为[2], [1], [1, 3], [2, 3], [3].
分析: