矢量挑战：如何根据 max/min 条件拆分矢量

Question

我最近遇到了以下问题：

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

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

例如，[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;
}

Answer 1

我认为你应该看看 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 的长度。从这里开始，您的事情可能会变得更容易。

矢量挑战：如何根据 max/min 条件拆分矢量

Challenge with vector: how to split a vector based on max/min conditions

vector

minmax