1

我在一次编程面试中遇到了这个问题，现在还不知道。

一个长度为n的列表，其中的元素都是无序的正整数。找出所有可能的三元组 (a, b, c)，即 a < b < c，并且 a 在列表中出现在 b 之前和 b 在 c 之前。

并分析算法的时间复杂度。

4

3 回答 3

4

没有通用算法比 O(n^3) 更快，因为给定不同元素的排序输入，那么输出的大小将为 O(n^3)，因此仅产生输出将需要时间成比例。实际上，即使是随机生成的整数列表也已经有 n^3 三倍，直到常数因子。

鉴于您可以简单地按列表顺序迭代所有可能的三元组，并比较它们的排序顺序。这个幼稚的解决方案已经是渐近最好的（即 O(n^3)）

for (int i = 0; i < n; i++)
    for (int j = i+1; j < n; j++)
        for (int k = j+1; k < n; k++)
            if (X[i] < X[j] && X[j] < X[k)
                output(X[i],X[j],X[k])

我怀疑您的问题陈述中可能存在转录错误-否则该问题应该是一个非常简单的简短编码练习。

于 2012-10-16T06:43:03.210 回答
3

如果已知只有一小组三元组（例如 k），那么您可能更愿意通过存储指向前一个最小元素的指针来查找所有三元组。

算法

准备一个空的数据结构（可能的选择稍后描述）。

准备一个长度为 n 的空数组 B。

然后对于列表中的每个元素 c：

  1. 使用数据结构存储列表中小于 c（如果存在）的最新元素的索引（在数组 B 中）。
  2. 在数据结构中存储 c（及其在原始列表中的索引）
  3. 然后使用数组 B 找到所有 b 小于 c 的元素，然后再次找到所有 a 小于 b 的元素，并将所有这些组合作为输出三元组发出。

数据结构

数据结构需要能够存储值、位置对，以便轻松找到所有值小于 c 的元素的最大位置（即最近的位置）。

如果允许值的范围相当小，一种简单的方法是使用一系列数组，其中 A[k][x] 存储范围 [x*2^k,(x+ 1)*2^k)。

如果值最多有 M 位（即值在 0 到 2^M-1 范围内），则更新或访问此数据结构都是 O(M) 操作。

复杂

给定的方法是 O(nM+k)。

如果值的范围更大，那么您可以使用二叉搜索树的形式而不是一系列数组，或者对值进行排序并用它们的序数值替换这些值。这将具有复杂性 O(nlogn+k)。

数三倍

如果你只是想知道这种形式的三元组的总数，那么你可以在 O(n) 中做到这一点。

思路和之前类似：

  1. 查找每个索引的最近的较小元素，以及每个索引的较小元素的计数
  2. 查找每个索引的下一个更大元素，以及更大元素的计数
  3. 计算每个索引的较小元素计数和较大元素计数的乘积之和。

为了实现这个 O(n)，我们需要能够在 O(n) 中找到下一个更大的元素。这可以通过以下方式完成：

  1. 将当前索引 i 推入堆栈
  2. 当 A[top(stack)] < A[i+1] 时，从堆栈中弹出一个索引 x 并存储 NGE[x]=i+1
  3. 增加 i 并返回步骤 1

我们还需要能够在 O(n) 中找到更大元素的计数。一旦准备好 NGE 数组，我们可以通过向后迭代数组和计算来找到计数

count_greater_elements[i] = count_greater_elements[ NGE[i] ] + 1 if NGE[i] is defined
                          = 0 otherwise

最近的较小元素和计数可以以类似的方式计算。

于 2012-10-16T07:25:16.820 回答
2

一般情况下的 N^2 解决方案（计算所有这样的三元组，而不是全部输出；输出将采用 n^3 只是因为它的大小）：

对于数组中的每个数字 X，让我们计算小于 X 且索引小于 x 的数字数量和大于 X 且索引大于 X 的数字数量。对于每个 X，我们可以获得其中 X 是中间元素的三元组的数量作为更少[X] * 更大[X]。答案是这些产品的总和。

int calc(vector<int> numbers) {
 int n = numbers.size();
 vector<int> less(n), more(n);
 for (int i = 0; i < n; i++)
  for (int j = i + 1; j < n; j++)
   if (numbers[i] < numbers[j])
    less[j]++, more[i]++;

 int res = 0;
 for (int i = 0; i < n; i++)
  res += less[i] * more[i];

 return res;
}
于 2012-10-16T17:28:00.913 回答