arrays - 检查数组的子数组的所有元素是否不存在于数组的其余部分

Question

假设我们有一个数组 a = { ... } 我们应该回答一些查询，每个查询包含 2 个索引 l 和 r ，每个查询的答案是 YES 或 NO :

是:如果子数组 [l,r] 的所有元素都不存在于数组的其余部分(段 [1,l-1] 和段 [r+1,n] )。

否:否则

我能想到的最好的办法是 o(n^3) 解决方案:迭代每个片段 (i,j) 需要 O(n^2) 然后为每个片段检查该片段的所有元素所以它是 O( n^3) 整体。

我至少需要 O(n^2) 的解决方案或一些提示，谢谢。

例如:a = [4, 4, 2, 5, 2, 3]查询:

1 2 -> 是

3 5 -> 是

2 3 -> 否

4 6 -> 否

Answer 1

预处理:遍历数组并创建 HashMap counts每个元素出现在数组中的次数。

对于每个查询:遍历子数组并创建一个 hashmap queryCounts存储每个元素的计数。查找 queryCounts 的每个元素在 counts并比较计数 - 如果所有计数都匹配则返回"is"，否则返回“否”。

运行时间:预期O(n) 预处理和每个查询 O(n)。

伪代码:

(假设当您尝试访问 map 中不存在的元素时，它们将被初始化为 0，类似于 C++ 的 std::map)

预处理:

array[n] // the input array

Map<int -> int> counts
for i = 1 to n
   counts[array[i]]++

查询i j :

Map<int -> int> queryCounts
for x = i to j
   queryCounts[array[x]]++
for each key y in queryCounts
   if queryCounts[y] != counts[y]
      return "no"
return "yes"

示例:

数组:[4, 4, 2, 5, 2, 3]

HashMap 将是:

2 -> 2
3 -> 1
4 -> 2
5 -> 1

如有疑问3 4 (基于 1)在子数组 [2, 5] 上，我们将得到:

2 -> 1
5 -> 1

我们将其与第一个 HashMap 进行比较，发现 2 的计数不匹配，所以我们返回“否”。

---

---

替代方法:

您还可以在预处理期间遍历所有子数组并存储是否返回"is"或“否”以获得 O(n²) 预处理和 O(1) 每个查询。

注意 [i,j] 的 hashmap可以从[i,j-1]获得的 hashmap 通过将 array[j] 的计数加 1 ，因此如果我们跟踪错误的计数数量并且只检查如何更改 array[j]，我们只需要在预处理期间对每个子数组执行 O(1) 工作的计数将更改此数字。

伪代码:

预处理:

array[n] // the input array

Map<(int, int) -> String> queryResults
for i = 1 to n
   Map<int -> int> queryCounts // clear on every i iteration
   countsWrong = 0
   for j = i to n
      if queryCounts[array[j]] == counts[array[j]]
         countsWrong++ // the counts match, the below operation will make it not match
      queryCounts[array[j]]++
      if queryCounts[array[j]] == counts[array[j]]
         countsWrong--
      if countsWrong == 0
         queryResults[i,j] = "yes"
      else
         queryResults[i,j] = "no"

查询i j :

return queryResults[i,j]

示例:

数组:[4, 4, 2]

HashMap 将是:

2 -> 1
4 -> 2

我们从 i=1, j=1 开始:

4 -> 1
countsWrong = 1 // since 4's count is wrong (not 2)
queryResults[1,1] = "no"

对于 i=1, j=2 ，我们将 1 加到 4 的计数:

4 -> 2
countsWrong = 0 // 4's count is now right
queryResults[1,2] = "yes"

对于 i=1, j=3 ，我们将 1 添加到 2 的计数:

4 -> 2
2 -> 1
countsWrong = 1 // 2's count is right
queryResults[1,3] = "yes"

对于 i=2, j=2 ，我们重置 map 和 1 到 4 的计数:

4 -> 1
countsWrong = 1 // 4's count is wrong (not 2)
queryResults[2,2] = "no"

对于 i=2, j=3 ，我们将 1 添加到 2 的计数:

4 -> 1
2 -> 1
countsWrong = 1 // 2's count is right, 4's is wrong (not 2)
queryResults[2,3] = "no"

对于 i=3, j=3 ，我们重置 map 和 1 到 2 的计数:

2 -> 1
countsWrong = 0 // 2's count is right
queryResults[1,2] = "yes"