17

给定一个未排序的正整数数组，求排序后元素连续的最长子数组的长度。你能想到一个 O(n) 的解决方案吗？

例子：

{10, 5, 3, 1, 4, 2, 8, 7}，答案是 5。

{4, 5, 1, 5, 7, 6, 8, 4, 1}，答案是 5。

对于第一个例子，子数组{5, 3, 1, 4, 2}在排序后可以形成一个最长的连续序列1,2,3,4,5。

对于第二个示例，子数组 {5, 7, 6, 8, 4} 是结果子数组。

我可以想到一种方法，对于每个子数组，检查 (maximum - minimum + 1) 是否等于该子数组的长度，如果为真，则它是一个连续子数组。取最长的。但它是 O(n^2) 并且不能处理重复。

有人可以提供更好的方法吗？

4

7 回答 7

2

解决 O(n) 中没有重复的原始问题的算法。也许，它可以帮助某人开发处理重复的 O(n) 解决方案。

输入：[a1, a2, a3, ...]

将原始数组映射为对，其中第一个元素是一个值，第二个元素是数组的索引。

数组：[[a1, i1], [a2, i2], [a3, i3], ...]

使用一些 O(n) 算法（例如计数排序）对这个对数组进行排序，以便按值进行整数排序。我们得到另一个数组：

数组：[[a3, i3], [a2, i2], [a1, i1], ...]

其中 a3, a2, a1, ... 按排序顺序排列。

通过对的排序数组运行循环

在线性时间内，我们可以检测到连续的数字组 a3、a2、a1。连续的组定义是下一个值 = 上一个值 + 1。在该扫描期间，保持当前组大小 ( n )、索引的最小值 ( min ) 和索引的当前总和 ( actualSum )。

在连续组内的每个步骤上，我们可以估计索引的总和，因为它们创建了具有第一个元素min、 step 1和到目前为止看到的组大小n的算术级数。这个总和估计可以使用算术级数公式在 O(1) 时间内完成：

估计总和 = (a1 + an) * n / 2;

估计总和 = (min + min + (n - 1)) * n / 2;

估计总和 = min * n + n * (n - 1) / 2；

如果在连续组内的某个循环步骤上估计总和等于实际总和，则到目前为止看到的连续组满足条件。将n保存为当前最大值结果，或在当前最大值和n之间选择最大值。

如果在值元素上我们不再看到连续组，则重置所有值并执行相同操作。

代码示例：https ://gist.github.com/mishadoff/5371821

于 2013-04-13T12:24:01.427 回答
1

这将需要对数据进行两次传递。首先创建一个哈希映射，将整数映射到布尔值。我更新了我的算法以不使用来自 STL 的地图，我很肯定它在内部使用排序。该算法使用散列，并且可以轻松更新任何最大或最小组合，甚至可能是整数可以获得的所有可能值。

#include <iostream>

using namespace std;
const int MINIMUM = 0;
const int MAXIMUM = 100;
const unsigned int ARRAY_SIZE = MAXIMUM - MINIMUM;

int main() {

bool* hashOfIntegers = new bool[ARRAY_SIZE];
//const int someArrayOfIntegers[] = {10, 9, 8, 6, 5, 3, 1, 4, 2, 8, 7};
//const int someArrayOfIntegers[] = {10, 6, 5, 3, 1, 4, 2, 8, 7};
const int someArrayOfIntegers[] = {-2, -3, 8, 6, 12, 14,  4, 0, 16, 18, 20};
const int SIZE_OF_ARRAY = 11;

//Initialize hashOfIntegers values to false, probably unnecessary but good practice.
for(unsigned int i = 0; i < ARRAY_SIZE; i++) {
    hashOfIntegers[i] = false;
}

//Chage appropriate values to true.
for(int i = 0; i < SIZE_OF_ARRAY; i++) {
    //We subtract the MINIMUM value to normalize the MINIMUM value to a zero index for negative numbers.
    hashOfIntegers[someArrayOfIntegers[i] - MINIMUM] = true;
}

int sequence = 0;
int maxSequence = 0;
//Find the maximum sequence in the values
for(unsigned int i = 0; i < ARRAY_SIZE; i++) {

    if(hashOfIntegers[i]) sequence++;
    else sequence = 0;

    if(sequence > maxSequence) maxSequence = sequence;
}

cout << "MAX SEQUENCE: " << maxSequence << endl;
return 0;
}

基本思想是将哈希映射用作桶排序，这样您只需对数据进行两次传递。这个算法是 O(2n)，而这又是 O(n)

于 2013-05-01T14:32:22.800 回答
1

在它的数学集合定义中查看数组S ：

S = U j = 0 k (我j )

其中I j是不相交的整数段。您可以设计一个特定的区间树（基于您喜欢的红黑树或自平衡树:)）以将数组存储在此数学定义中。节点和树结构应如下所示：

struct node {
    int d, u;
    int count;
    struct node *n_left, *n_right;
}

这里，d 是整数段的下界，u 是上界。添加以处理数组中可能的重复项：当尝试在树中插入一个已经存在的元素时，我们将增加找到它的节点count的值，而不是什么都不做。count

struct root {
    struct node *root;
}

树只会存储不相交的节点，因此，插入比经典的红黑树插入要复杂一些。插入间隔时，您必须扫描现有间隔的潜在溢出。在您的情况下，由于您只会插入单例，因此不应增加太多开销。

给定三个节点 P、L 和 R，L 是 P 的左孩子，R 是 P 的右孩子。然后，您必须强制 Lu < Pd 和 Pu < Rd（当然，对于每个节点，d <= u） .

插入整数段 [x,y] 时，必须找到“重叠”段，即满足以下不等式之一的区间 [u,d]：

y >= d - 1
或
x <= u + 1

如果插入的区间是单例x，那么您最多只能找到 2 个重叠区间节点 N1 和 N2 使得N1.d == x + 1和N2.u == x - 1。然后你必须合并这两个区间并更新计数，这样你就可以得到 N3 N3.d = N2.d，N3.u = N1.u和N3.count = N1.count + N2.count + 1。由于 和 之间N1.d的N2.u增量是两个分段不相交的最小增量，因此您必须具有以下条件之一：

  • N1 是 N2 的右孩子
  • N2 是 N1 的左孩子

所以插入仍然会在O(log(n))最坏的情况下。

从这里开始，我无法弄清楚如何处理初始序列中的顺序，但这里有一个可能很有趣的结果：如果输入数组定义了一个完美的整数段，那么树只有一个节点。

于 2013-04-12T12:53:14.130 回答
1

UPD2：以下解决方案是针对不需要子数组连续的问题。我误解了问题陈述。不删除这个，因为有人可能有一个基于我的想法，可以解决实际问题。

这是我想出的：

创建一个字典的实例（它被实现为哈希表，在正常情况下给出 O(1)）。键是整数，值是整数的哈希集（也是 O(1)） - var D = new Dictionary<int, HashSet<int>>。

遍历数组A并为每个n带有索引的整数i做：

  1. 检查键n-1和n+1是否包含在D.
    • 如果两个键都不存在，请执行D.Add(n, new HashSet<int>)
    • 如果只有一个键存在，例如n-1，做D.Add(n, D[n-1])
    • 如果两个键都存在，请执行D[n-1].UnionWith(D[n+1]); D[n+1] = D[n] = D[n-1];
  2. D[n].Add(n)

现在遍历每个键D并找到具有最大长度的哈希集（查找长度为 O(1)）。最大的长度将是答案。

据我了解，最坏情况的复杂性将是 O(n*log(n))，这仅仅是因为UnionWith操作。我不知道如何计算平均复杂度，但它应该接近 O(n)。如果我错了，请纠正我。

UPD：要说代码，这是 C# 中的测试实现，它在 OP 的两个示例中都给出了正确的结果：

var A = new int[] {4, 5, 1, 5, 7, 6, 8, 4, 1};
var D = new Dictionary<int, HashSet<int>>();

foreach(int n in A)
{
    if(D.ContainsKey(n-1) && D.ContainsKey(n+1))
    {
        D[n-1].UnionWith(D[n+1]);
        D[n+1] = D[n] = D[n-1];
    }
    else if(D.ContainsKey(n-1))
    {
        D[n] = D[n-1];
    }
    else if(D.ContainsKey(n+1))
    {
        D[n] = D[n+1];
    }
    else if(!D.ContainsKey(n))
    {
        D.Add(n, new HashSet<int>());
    }

    D[n].Add(n);
}

int result = int.MinValue;
foreach(HashSet<int> H in D.Values)
{
    if(H.Count > result)
    {
        result = H.Count;
    }
}

Console.WriteLine(result);
于 2013-04-12T12:00:50.373 回答
0

不要抱太大希望，这只是部分答案。

我很有信心这个问题在O(n). 不幸的是，我无法证明这一点。

如果有办法在小于的时间内解决它O(n^2)，我怀疑该解决方案基于以下策略：

  1. 确定O(n)（或者可能O(n log n)）是否存在一个连续的子数组，正如你用至少i元素描述的那样。让我们称之为谓词E(i)。
  2. i使用二分法来找到E(i)保持的最大值。

该算法的总运行时间将是O(n log n)（或O(n log^2 n)）。

这是我能想出的将问题简化为另一个问题的唯一方法，该问题至少有可能比原始公式更简单。但是，我找不到E(i)在小于的时间内计算的方法O(n^2)，所以我可能完全离开了......

于 2013-04-12T11:59:32.647 回答
-1

这是考虑问题的另一种方式：假设您有一个仅由 1 和 0 组成的数组，您想找到最长连续运行的 1。这可以通过对 1 进行游程编码（忽略 0）在线性时间内完成。为了将您的原始问题转换为这个新的运行长度编码问题，您需要计算一个新数组 b[i] = (a[i] < a[i+1])。这不必显式地完成，您可以隐式地完成它以实现具有恒定内存需求和线性复杂度的算法。

于 2013-05-01T05:47:24.300 回答
-2

以下是 3 个可接受的解决方案：

第一个O(nlog(n))在时间和O(n)空间上，第二个O(n)在时间和O(n)空间上，第三个O(n)在时间和O(1)空间上。

  1. 构建一个binary search tree然后按顺序遍历它。
    保留 2 个指针，一个用于最大子集的开始，一个用于结束。max_size在迭代树时保持值。这是一个O(n*log(n))时间和空间的复杂性。

  2. 您始终可以在线性时间内对使用计数排序设置的数字进行排序并遍历数组，这意味着O(n)时间和空间复杂度。

  3. 假设没有溢出或大整数数据类型。假设数组是一个数学集（没有重复值）。您可以在O(1)内存中执行此操作：

    • 计算数组的总和和数组的乘积
    • 假设您拥有原始集合的最小值和最大值，请找出其中的数字。完全是O(n)时间复杂度。
于 2013-04-12T11:54:31.667 回答