13

我想找到一种算法来计算数组的不同子数组的数量。

例如，在A = [1,2,1,2]的情况下，不同子数组的数量为 7：

{ [1] , [2] , [1,2] , [2,1] , [1,2,1] , [2,1,2], [1,2,1,2]}

在B = [1,1,1]的情况下，不同子数组的数量为 3： 

{ [1] , [1,1] , [1,1,1] }

子数组是数组的连续子序列或切片。不同的意思是不同的内容；例如：

来自 A[0:1] 的 [1] 和来自 A[2:3] 的 [1] 没有区别。

同样：

B[0:1]、B[1:2]、B[2:3] 没有区别。

4

6 回答 6

9

为这个数组构造后缀树。然后将这棵树中所有边的长度相加。

使用适当的算法（Ukkonen 或 McCreight 算法）构建后缀树所需的时间是 O(n)。遍历树并将长度加在一起所需的时间也是 O(n)。

于 2013-07-07T16:40:32.000 回答
1

您可以轻松地制作一组子序列并计算它们，但我不确定这是最有效的方法，因为它是O(n^2)。

在 python 中是这样的：

subs = [tuple(A[i:j]) for i in range(0, len(A)) for j in range(i + 1, len(A) + 1)]

uniqSubs = set(subs)

这给了你：

set([(1, 2), (1, 2, 1), (1,), (1, 2, 1, 2), (2,), (2, 1), (2, 1, 2)])

理解中的双循环清楚地说明了O(n²)复杂性。

编辑

显然有一些关于复杂性的讨论。潜艇的创建是O(n^2)因为有n^2项目。

O(m)从列表中创建集合是列表m的大小，m在n^2这种情况下，添加到集合是摊销的O(1)。

因此总体是O(n^2)。

于 2013-07-07T15:31:33.003 回答
1

编辑：我考虑如何减少迭代/比较数。我找到了一种方法：如果你检索一个大小为 n 的子数组，那么每个大小小于 n 的子数组都将被添加。

这是更新的代码。

    List<Integer> A = new ArrayList<Integer>();
    A.add(1);
    A.add(2);
    A.add(1);
    A.add(2);

    System.out.println("global list to study: " + A);

    //global list
    List<List<Integer>> listOfUniqueList = new ArrayList<List<Integer>>();      

    // iterate on 1st position in list, start at 0
    for (int initialPos=0; initialPos<A.size(); initialPos++) {

        // iterate on liste size, start on full list and then decrease size
        for (int currentListSize=A.size()-initialPos; currentListSize>0; currentListSize--) {

            //initialize current list.
            List<Integer> currentList = new ArrayList<Integer>();

            // iterate on each (corresponding) int of global list
            for ( int i = 0; i<currentListSize; i++) {
                currentList.add(A.get(initialPos+i));
            }

            // insure unicity
            if (!listOfUniqueList.contains(currentList)){
                listOfUniqueList.add(currentList);                      
            } else {
                continue;
            }
        }
    }

System.out.println("list retrieved: " + listOfUniqueList);
System.out.println("size of list retrieved: " + listOfUniqueList.size());

要研究的全局列表：[1, 2, 1, 2]

检索到的列表：[[1, 2, 1, 2], [1, 2, 1], [1, 2], [1], [2, 1, 2], [2, 1], [2]]

检索到的列表大小：7

使用包含相同模式的列表多次迭代和比较的次数将非常低。对于您的示例 [1, 2, 1, 2]， if (!listOfUniqueList.contains(currentList)){ 行执行了 10 次。对于包含 15 个不同子数组的输入 [1, 2, 1, 2, 1, 2, 1, 2]，它只提高到 36。

于 2013-07-07T16:39:57.220 回答
0

是的，我的第一个答案有点像金发女郎。

我想答案是全部生成它们，然后删除重复项。或者，如果您使用带有集合对象的 Java 之类的语言，则创建所有数组并将它们添加到一组 int[]。集合仅包含每个元素的一个实例并自动删除重复项，因此您可以在最后获取集合的大小

于 2013-07-07T15:15:43.933 回答
0

我可以想到2种方法...

首先是计算某种哈希，然后添加到一个集合中。如果在添加哈希时与现有数组相同...然后进行详细比较...并记录它，以便您知道您的哈希算法不够好...

第二个是使用某种可能的匹配，然后从那里向下钻取......如果元素的数量相同并且添加在一起的元素的总数相同，那么详细检查。

于 2013-07-07T16:06:24.490 回答
0

创建一个pair数组，其中每对存储子数组元素的值及其索引。 

pair[i] = (A[i],i);

按 的升序A[i]和的降序对这对进行排序i。

考虑排序后的示例A = [1,3,6,3,6,3,1,3];
对数组将是pair = [(1,6),(1,0),(3,7),(3,5),(3,3),(3,1),(6,4),(6,2)]

pair[0]有 的元素index 6。从index 6我们可以有两个子数组[1]和[1,3]。所以ANS = 2;
现在把每一对连续的一对一个接一个。
取pair[0]和pair[1]，
pair[1]索引为 0。我们可以有 8 个从 开始的子数组index 0。但是已经计算了两个子数组 [1] 和 [1,3]。所以要删除它们，我们需要比较 和 的子数组的最长公共pair[0]前缀pair[1]。因此，从 0 和 6 开始的索引的最长公共前缀长度是 2 即[1,3]。
所以现在新的不同子数组将是[1,3,6].. 到[1,3,6,3,6,3,1,3]6 个子数组。所以新的值为ANS2+6 = 8;

所以对于pair[i]和pair[i+1]
ANS = ANS + Number of sub-arrays beginning from pair[i+1] - Length of longest common prefix。

排序部分需要 O(n logn)。
迭代每个连续对是 O(n) 并且对于每次迭代，找到最长的公共前缀需要 O(n) 使得整个迭代部分 O(n^2)。这是我能得到的最好的。

您可以看到我们不需要为此配对。对的第一个值，元素的值不是必需的。我用它来更好地理解。你总是可以跳过那个。

于 2013-07-07T16:19:41.770 回答