1

我最近遇到了以下问题：

假设我有一个随机长度 (L) 为 0 和 1 的向量随机分布（例如 [0,1,1,1,0,0,1,0]），我需要将向量分成两个子索引 K 处的向量，因此以下条件有效：

  • 左子向量必须包含来自 K 的逆序元素的最大数量，例如零的数量必须大于或等于 1 的数量
  • 右子向量必须包含从 K+1 开始的最大元素个数，例如 1 的个数必须大于或等于零的个数

例如， [1,1,1,1,1,1,1,1,1,0,1,0,0,0,0,0,0,0,0] 拆分位于索引 9，左侧向量为[1,0]，右向量为[0,1]

我编写了以下解决方案，但复杂度为 O(L^2)。我认为可能有一个复杂的最坏情况 O(L) 的解决方案，但我找不到任何可以帮助我的东西。任何想法？谢谢

var max = 0;
var kMax = -1;

var firstZeroFound = false;

for (var i = 0; i < testVector.Length - 1; i++)
{
    if (!firstZeroFound)
    {
        if (testVector[i]) continue;
        firstZeroFound = true;
    }

    var maxZero = FindMax(testVector, i, -1, -1, false);
    if (maxZero == 0) continue;

    var maxOne = FindMax(testVector, i + 1, testVector.Length, 1, true);
    if (maxOne == 0) continue;

    if ((maxZero + maxOne) <= max)
        continue;

    max = maxOne + maxZero;
    kMax = i;

    if (max == testVector.Length)
        break;
}

Console.Write("The result is {0}", kMax); 

int FindMax(bool[] v, int start, int end, int increment, bool maximize)
{
    var max = 0;
    var sum = 0;
    var count = 0;
    var i = start;

    while (i != end)
    {
        count++;

        if (v[i])
            sum++;

        if (maximize)
        {
            if (sum * 2 >= count)
                max = count;
        }
        else if (sum * 2 <= count)
        {
            max = count;
        }

        i += increment;
    }

    return max;
}
4

1 回答 1

2

我觉得你应该看看rle。

    y <- c(1,1,1,1,1,1,1,1,1,0,1,0,0,0,0,0,0,0,0)
    z <- rle(y)
    d <- cbind(z$values, z$lengths)
        [,1] [,2]
[1,]    1    9
[2,]    0    1
[3,]    1    1
[4,]    0    8

基本上，rle计算每个级别的 0 和 1 的长度。从这里开始，事情可能会变得更容易。

于 2016-03-08T17:50:25.010 回答