时间戳

首页 > 解决方案 > 可能的不同子数组

java - 可能的不同子数组

问题描述

获取许多可能的不同子数组，使得它们最多具有给定数量的奇数。

例子：

arr = [2,1,2,1,3]
m = 2.

回答：

10

解释：

所以总共有 10 个可能的不同子数组。

约束：

数组大小最多可包含 1000 个元素，m 的范围可以从 1 到数组大小。

public static int process(List<Integer> arr, int m) {
    Set<String> set = new LinkedHashSet<>();
    for (int i = 0; i < arr.size(); i++) {
        for (int j = i; j < arr.size(); j++) {
            int odd = 0;
            StringBuilder sb = new StringBuilder();
            for (int k1 = i; k1 <= j; k1++) {
                if (arr.get(k1) % 2 != 0) {
                    odd++;
                }
                sb.append(arr.get(k1) + " ");
            }
            if (odd <= m) {
                set.add(sb.toString());
            }

        }
    }
    return set.size();
}

该程序适用于小输入，但由于我有 3 个 for 循环，因此对于大输入失败。解决这个程序的正确方法是什么？

我已经浏览过这篇文章 -查找具有指定奇数个数的子数组的数量，但这里的问题没有考虑不同的子数组。

标签： javaalgorithm

解决方案

这是一个 O(n^2) 方法：

  1. 假设元素存储在大小为 n+1 的数组中，位置为 [1....n]
  2. 让我们相应地修改数组：A[0]=0和A[i] = A[i-1] + (A[i]%2==1 ? 1 : 0)，所以现在 A[i] 存储范围 [0...i] 中的奇数个数
  3. 注意某些范围内的奇数计数[i,j]现在与A[j]-A[i-1]
  4. 现在只需检查 O(n^2) 中的所有可能范围
  5. 对于不同的子数组，我们可以使用 Set/Hash 数据结构，但我们需要有效地存储子数组
  6. 最有效的似乎是散列，我们可以使用一些基 b 和模 m 进行多项式散列，这样H[0] = 0, H[i] = H[i-1] * b + A[i] % m如果 a 和 m 是大于最大输入值的素数，它应该可以工作

伪代码：

int res = 0;

for(int i=1; i<=n; i++)
 A[i] = A[i-1] + (A[i]%2 == 1);

for(int i=1; i<=n; i++)
for(int j=i; j<=n; j++)
  res+=A[j]-A[i-1] <= m;

推荐阅读