c# - 哪个角落案例单元测试会失败？

Question

我尝试了 Fish problem on Codility我的正确性得到了 75% 的分数，因为结果报告说我的代码没有通过一个简单的测试用例。结果不报告为测试用例提供了什么输入。

你能帮我找出我的代码有什么问题以及它会失败的极端情况吗？

using System;

public class Solution
{
    // Time complexity: O(N)
    // Space complexity: O(N)
    public int solution(int[] sizes, int[] direction)
    {
        if (sizes == null || direction == null)
            throw new ArgumentNullException();

        var sizesLen = sizes.Length;
        var directionLen = direction.Length;

        if (sizesLen != direction.Length)
            throw new ArgumentException();

        var len = sizesLen;

        if (len <= 1) return len;

        var survivors = new Fish[len];
        survivors[0] = new Fish(sizes[0], direction[0]);
        var curr = 0;

        for (int i = 1; i < len; i++)
        {
            var fish = new Fish(sizes[i], direction[i]);

            if (survivors[curr].Direction == 1 && fish.Direction == 0)
            {
                if (fish.Size < survivors[curr].Size) continue;

                while(curr >= 0 && 
                    fish.Size > survivors[curr].Size && 
                    survivors[curr].Direction == 1)
                {
                    curr--;
                }
            }

            survivors[++curr] = fish;
        }

        return ++curr;
    }
}

public class Fish
{
    public Fish(int size, int direction)
    {
        Size = size;
        Direction = direction;
    }

    public int Size { get; set; }
    public int Direction { get; set; }
}

Answer 1

如您的代码中所述，您的解决方案是O(M*N)。如问题链接中所述，代码应以线性时间运行。因此，我不会更正您的解决方案，因为它最终会在更大的测试用例上失败。我将为您提供一个您可以轻松实现的线性算法。

保留一个 Stack S，最初是空的。

遍历数组A，i从0到n-1

当你遇到一个元素，比如说A[i]，做下面的事情

• 如果堆栈 S 为空，则将 (A[i], B[i]) 成对压入

• 否则，从堆栈 S 中提取顶对并比较 B[top] 和 B[i]。

  虽然 B[top] 是1 并且B[i] 是0，则其中一条鱼会吃掉另一条鱼。所以从堆栈 S 中弹出栈顶元素。现在，用值 A[top] 和 A[i] 比较哪条鱼更大。无论哪个更大，那条鱼都会活着。将该对插入堆栈 S，它对应于存活的鱼。继续 while 循环直到条件失败如果 B[top] 不是 1 并且 B[i] 不是 0，那么只需推送新的对 (A[i],B[i])

最后堆栈 S 的大小就是你的答案。

注意:您可能没有通过该测试用例，因为您的解决方案会超时。例如，对于 N=100000，您的解决方案将超时。

在我的解决方案中，最坏情况下的时间复杂度是 O(N+N) = O(2N) = O(N) . N 次，因为对数组 A 的迭代和另一个 N 次最坏情况，由于 Stack 如果它不断缩小，对于 while 条件成立 true。

希望对您有所帮助!!!

编辑:假设 A = [ 99, 98, 92, 91, 93 ]，B = [1, 1, 1, 1, 0]。您的代码给出的答案为 3。预期答案 = 2

Edit-2:这是您修改后的代码，将通过每个测试用例

public int solution(int[] sizes, int[] direction)
    {
        if (sizes == null || direction == null)
            throw new ArgumentNullException();

        var sizesLen = sizes.Length;
        var directionLen = direction.Length;

        if (sizesLen != direction.Length)
            throw new ArgumentException();

        var len = sizesLen;

        if (len <= 1) return len;

        var survivors = new Fish[len];
        survivors[0] = new Fish(sizes[0], direction[0]);
        var curr = 0;

        for (int i = 1; i < len; i++)
        {
            var fish = new Fish(sizes[i], direction[i]);

            if (survivors[curr].Direction == 1 && fish.Direction == 0)
            {
                if (fish.Size < survivors[curr].Size) continue;

                while(curr >= 0 && 
                    fish.Size > survivors[curr].Size && 
                    survivors[curr].Direction == 1)
                {
                    curr--;
                }

                if (curr >= 0)
                {
                    if (fish.Size < survivors[curr].Size && 
                         survivors[curr].Direction == 1) 
                               continue;
                }
            }

            survivors[++curr] = fish;
        }

        return ++curr;
    }

}

public class Fish
{
    public Fish(int size, int direction)
    {
        Size = size;
        Direction = direction;
    }

    public int Size { get; set; }
    public int Direction { get; set; }
}