查找数组中重复子数组的个数 [英] Find the number of repeated subarray in an array

问题描述

有一个从 0-n 索引的数组(即 size=n)包含来自 0-m 的元素，其中 m (假设m比n小100或1000倍，即m远小于n)，所以很多元素或子数组必须重复，我们必须找到这种重复大小的子数组的数量1 或多于 1.例如，考虑一个数组
1 2 4 1 2 4 1 5 6 3 5，这里
1 重复 2 次
2 重复 1 次
4 重复 1 次
5 重复 1 次
1 2 重复 1 次
2 4 重复 1 次
4 1重复1次
1 2 4重复1次
2 4 1重复1次
1 2 4 1重复1次
所以最终答案是这些的总和，即 11
任何人都可以建议一些数据结构或有效的算法来解决这个问题.我正在考虑散列 m 并注意它出现的索引值，但没有对其进行形式化.
假设 n,m <10^5

There is an array indexed from 0-n (i.e. size=n) containing elements from 0-m where m < n (assume m is 100 or 1000 times less than n i.e. m is much less than n), so many of the elements or sub array must be repeated and we have to find the number of such repeated sub array of size 1 or more than 1. For example, consider an array
1 2 4 1 2 4 1 5 6 3 5, here
1 is repeated 2 times
2 is repeated 1 time
4 is repeated 1 time
5 is repeated 1 time
1 2 is repeated 1 time
2 4 is repeated 1 time
4 1 is repeated 1 time
1 2 4 is repeated 1 time
2 4 1 is repeated 1 time
1 2 4 1 is repeated 1 time
So the final answer is sum of these i.e. 11
Can anybody please suggest some data structure or an efficient algorithm to solve this. I was thinking of hashing m and noting the index value where it occurs but didn't formalize it.
Assume n,m < 10^5

推荐答案

1. 创建一个以整数为键的散列，以及整数的可扩展列表(例如链接列表)作为值.

1. Create a hash that has integers as keys, and extendible lists (linked lists, e.g.) of integers as values.

通读您的输入列表.将每个被扫描的输入元素视为一个键；将以下元素的索引附加到关联的值列表.

Read through your input list. Treat each input element being scanned as a key; append the index of the following element to the associated list of values.

现在，您重复的 1 元素计数是 n - |keys|

Now, your repeated 1-element count is n - |keys|

接下来，检查你的钥匙.对于每个键，将原始列表的索引元素视为新的输入列表.创建一个新的散列并按照步骤 1 继续.请注意，当我们存储索引时，我们将继续使用原始列表的索引.

Next, go through your keys. For each key, treat the indexed elements of the original list as a new input list. Create a new hash and continue as in step 1. Note that when we store indices we continue to use those of the original list.

示例:1 2 4 1 2 4 1 5 6 3 5(假设我们是零索引的).这里，n=11.

Example: 1 2 4 1 2 4 1 5 6 3 5 (assume we're zero-indexed). Here, n=11.

• 1 -> [1, 4, 7]
• 2 -> [2, 5]
• 3 -> [10]
• 4 -> [3, 6]
• 5 -> [8，无]
• 6 -> [9]

重复 1-elt 的次数为 11 - 6 = 5.

The number of repeated 1-elts is 11 - 6 = 5.

现在，我们来看看钥匙.我们从 1 开始，索引列表是 ​​[1, 4, 7]，对应元素 [2, 2, 5].

Now, we go through the keys. We start with 1. The index list is [1, 4, 7] which corresponds with elements [2, 2, 5].

• 2 -> [2, 5]
• 5 -> [8]

这会选取 3 - 2 = 1 个重复的 2 元素列表.

This picks up 3 - 2 = 1 duplicate 2-element list.

等等...

运行时间:输入+输出线性

Running time: Linear in the input + output

这篇关于查找数组中重复子数组的个数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！