检查数组中的连续序列

Question

我正在尝试编写一个方法（public bool Seq_Check(int[] A, int k)），用于检查数组A是否包含数字1,2,...,k（每个数字至少出现一次），且不包含其他数字。

因此，对于myArr1和myArr2，它应该分别返回true和false，这也是正确的。但错误地显示第三个数组为true。

请问有人能帮我找到这里的错误吗？

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ArrayChecker
{
    class Program
    {
        /// The program's main entry point.
        static void Main(string[] args)
        {
            // Input arrays are assumed to be in non-decreasing order.
            int[] myArr1 = new int[] { 1, 1, 2, 3, 3 };
            int[] myArr2 = new int[] { 1, 1, 3 };
            int[] myArr3 = new int[] { 1, 1, 1, 2, 3, 4, 5, 6, 1 };

            // Printing to console True & False respectively.
            Console.WriteLine( Seq_Check(myArr1, 3) );
            Console.WriteLine( Seq_Check(myArr2, 2) );
            Console.WriteLine( Seq_Check(myArr3, 6) );

            // Prevent the console window from closing.
            Console.ReadLine();
        }


        /// This method checks whether array A contains numbers 1,2,...,k
        /// (every number from 1 to k exactly once) and no other numbers.
        public static bool Seq_Check(int[] A, int k)
        {
            int n = A.Length;

            for (int i = 0; i < n-1; i++)
            {
                if ( A[i]+1 < A[i+1] )
                    return false;
            }

            if ( A[0] != 1 && A[n-1] != k )
                return false;
            else
                return true;
        }
    }
}

- user285372

---

我不明白为什么对于 myArr4 它应该返回 false。 - Mehrzad Chehraz

你有经过Seq_check来查看哪一个return false语句正在执行吗？ - ChrisF

@MehrzadChehraz - 第二个参数 k 是6，所以应该是 1, 2, 3, 4, 5, 6，但实际上是 1,2,3,3,4,5,6（根据我的理解）。 - keyboardP

“6,1,2,3,4,5,6”应该返回true还是false？“6,1,2,3,4,5,6,1”呢？ - Preston Guillot

这两个数组中都有1..6的有序序列，你的问题陈述需要更多的定义。 - Preston Guillot

Answer 1

如果您使用Linq，可以使用Range()、Distinct()和Exclude()来完成您的任务...让Linq为您工作。

- John E

---

谢谢。我现在意识到开始学习 Linq 是多么重要了... - user285372

Answer 2

尝试一下。

        public static bool Seq_Check(int[] A, int k)
        {
            int n = A.Length;
            if (A[0] != 1 || A[n - 1] != k)//no need to go through array if it is already bad
                return false;

            for (int i = 0; i < n - 1; i++)
            {
                if (A[i] + 1 < A[i + 1])
                    return false;
            }
            return true;
        }

你在检查A[0]=1和A[n-1]=k时使用了&&而不是||。这意味着只要其中一个条件为真，函数就会返回true。你希望当任一条件为真时，函数应该返回false。

- drxl

Answer 3

第三个数组返回 true 的原因是因为 A[0] != 1 && A[n-1] != k 是 false。

我来解释一下。

A[0] != 1 我们称之为 X

数组中的第一个位置确实是1，所以返回 true。

A[n-1] != k 我们称之为 Y

最后一个位置不是6，所以返回 false。

因此，X && Y 是 false。

应该改成 A[0] != 1 || A[n-1] != k 吗？

- Michael

Answer 4

需要更改for循环中的主要检查：

if (A[i] + 1 < A[i+1] )
    return false;

首先，您需要检查顺序，因此您需要检查具有较高索引的元素是否大于前一个元素：

if (A[i] >= A[i+1])
    return false;

由于您不介意元素在系列开头或结尾相等，因此您需要添加另一个检查以避免在这些情况下返回false：

bool inSequence = A[i] != 1 || A[i] == k;
if (A[i] > A[i+1] || (A[i] == A[i+1] && inSequence))
  return false;

在这里，我们检查是否开始/结束的序列中有重复项，如果我们仍然在序列中，那么不允许重复项，因此A[i+1] == A[i]应该返回false。

public static bool Seq_Check(int[] A, int k)
{
    int n = A.Length;

    for (int i = 0; i < n - 1; i++)
    {
        bool inSequence = A[i] != 1 || A[i] == k;
        if (A[i] > A[i+1] || (A[i] == A[i+1] && inSequence))
            return false;
        }

    }
    if ( A[0] != 1 && A[n-1] != k )
        return false;
    else
        return true;     
 }

- Mehrzad Chehraz

Answer 5

据我所知，您想查看从1到K是否存在连续范围，除非数字位于范围的中间，否则重复数字不重要。

因此，对于[ 1, 1, 1, 2, 3, 4, 4, 5, 6, 1]，K为[2,3,4]的情况将通过，但[5, 6]将失败，因为4被重复了，打破了连续范围的链条。

为此，我会从后往前开始查找K的实例，然后从那里开始向后计数，如果能够到达1，则返回true。

public bool Seq_Check(int[] elems, int k)
{
    for(int i=elems.Length;i>0;i--)
    {
       //we found the first element we are looking for
       //so need to start looking for the rest of the sequence
       if(elems[i]==k)
       {
            // don't create a new index, we can reuse i
            int curr = k-1;
            for(;i>0 && curr>0;i--)
            {
                if(elems[i]!=curr) 
                {
                     if(elems[i]==k)
                     {
                         //reinitialize if we found K again
                         curr=k-1;
                         continue;
                     }
                     break;
                }

                curr--;
            }

            // if the curr value is 0 then 
            // we found all the elements
            if(curr == 0)
            {
                return true;
            }
       }
    }

    //no matching sequence was found so return false
    return false;
}

- konkked

Answer 6

这段代码给我的结果和你的一样。第三个数组是[1, 1, 1, 2, 3, 4, 5, 6, 1]，排序后的版本是[1, 1, 1, 1, 2, 3, 4, 5, 6]。它确实包含了范围[1, 6]内的所有数字。问题出在哪里呢？

namespace SequenceCheck
{
    using System;
    public class Program
    {
        public static void Main()
        {
            int[] myArr1 = new int[] { 1, 1, 2, 3, 3};
            int[] myArr2 = new int[] { 1, 1, 3 };
            int[] myArr3 = new int[] { 1, 1, 1, 2, 3, 4, 5, 6, 1 };

            // Printing to console True & False respectively.
            Console.WriteLine(Seq_Check(myArr1, 3));
            Console.WriteLine(Seq_Check(myArr2, 2));
            Console.WriteLine(Seq_Check(myArr3, 6));

        }
        public static bool Seq_Check(int[] A, int k)
        {
            // TODO Check for corner cases!

            // Let's at first sort the numbers
            Array.Sort(A);

            int start = 1, end = k;
            // If the first element is not equal to start, something wrong with sequence
            if (A[0] != start) return false;

            // If we here it means we checked 1, let go further
            int expected = start + 1;
            int currUnique = A[0];

            for (int i = 1; i < A.Length; i++)
            {
                // Is it new unique number?
                if (A[i] != A[i - 1])
                {
                    currUnique = A[i];
                    // Compare with expected and check is there any other numbers?
                    if (currUnique != expected || expected > end)
                        return false;
                    expected++;
                }

            }
            return true;
        }
    }
}

- Artavazd Balayan