7

给定两个数组作为参数（x 和 y），并找到 x 中第一次出现 y 的起始索引。我想知道最简单或最快的实现是什么。

例子：

when x = {1,2,4,2,3,4,5,6}
     y =       {2,3}
result
     starting index should be 3

更新：由于我的代码错误，我将其从问题中删除。

4

8 回答 8

8

最简单的写法？

    return (from i in Enumerable.Range(0, 1 + x.Length - y.Length)
            where x.Skip(i).Take(y.Length).SequenceEqual(y)
            select (int?)i).FirstOrDefault().GetValueOrDefault(-1);

当然，效率不高……更像是：

private static bool IsSubArrayEqual(int[] x, int[] y, int start) {
    for (int i = 0; i < y.Length; i++) {
        if (x[start++] != y[i]) return false;
    }
    return true;
}
public static int StartingIndex(this int[] x, int[] y) {
    int max = 1 + x.Length - y.Length;
    for(int i = 0 ; i < max ; i++) {
        if(IsSubArrayEqual(x,y,i)) return i;
    }
    return -1;
}
于 2009-11-23T00:00:08.903 回答
7

这是一个简单（但相当有效）的实现，它查找数组的所有出现，而不仅仅是第一个：

static class ArrayExtensions {

  public static IEnumerable<int> StartingIndex(this int[] x, int[] y) {
    IEnumerable<int> index = Enumerable.Range(0, x.Length - y.Length + 1);
    for (int i = 0; i < y.Length; i++) {
      index = index.Where(n => x[n + i] == y[i]).ToArray();
    }
    return index;
  }

}

例子：

int[] x = { 1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4 };
int[] y = { 2, 3 };
foreach (int i in x.StartingIndex(y)) {
  Console.WriteLine(i);
}

输出：

1
5
9

该方法首先遍历x数组以查找数组中第一项的所有出现y，并将它们的索引放置在index数组中。y然后它继续通过检查其中哪些也匹配数组中的第二项来减少匹配。当y检查数组中的所有项目时，index数组仅包含完整匹配项。

编辑：
另一种实现是ToArray从循环中的语句中删除调用，使其成为：

index = index.Where(n => x[n + i] == y[i]);

这将完全改变该方法的工作方式。它不是逐级循环遍历项目，而是返回一个带有嵌套表达式的枚举器，将搜索推迟到迭代枚举器的时间。这意味着如果您愿意，您只能获得第一场比赛：

int index = x.StartingIndex(y).First();

这不会找到所有匹配项然后返回第一个，它只会搜索直到找到第一个然后返回它。

于 2009-11-23T00:00:50.057 回答
4

最简单的方法大概是这样的：

public static class ArrayExtensions
{
    private static bool isMatch(int[] x, int[] y, int index)
    {
        for (int j = 0; j < y.Length; ++j)
            if (x[j + index] != y[j]) return false;
        return true;
    }

    public static int IndexOf(this int[] x, int[] y)
    {
        for (int i = 0; i < x.Length - y.Length + 1; ++i)
            if (isMatch(x, y, i)) return i;
        return -1;
    }
}

但这绝对不是最快的方法。

于 2009-11-22T23:58:28.580 回答
4

这是基于Mark Gravell 的回答，但我将其设为通用并添加了一些简单的边界检查以防止抛出异常

private static bool IsSubArrayEqual<T>(T[] source, T[] compare, int start) where T:IEquatable<T>
{
    if (compare.Length > source.Length - start)
    {
        //If the compare string is shorter than the test area it is not a match.
        return false;
    }

    for (int i = 0; i < compare.Length; i++)
    {
        if (source[start++].Equals(compare[i]) == false) return false;
    }
    return true;
}

可以通过实施Boyer-Moore进一步改进，但对于短模式它工作正常。

于 2012-05-10T15:00:27.083 回答
2

在这种情况下，“最简单”和“最快”是对立的，此外，为了描述快速算法，我们需要了解很多关于源数组和搜索数组如何相互关联的信息。

这与在字符串中查找子字符串本质上是相同的问题。假设您正在“快速棕色狐狸跳过懒狗”中寻找“狐狸”。在这种情况下，朴素的字符串匹配算法非常好。如果您在“banananananabanananananabananabananabananananananananana...”形式的百万字符字符串中搜索“bananananananananananananananananana”，那么简单的子字符串匹配算法很糟糕——使用更复杂和复杂的字符串匹配算法可以获得更快的结果. 基本上，朴素算法是 O(nm)，其中 n 和 m 是源字符串和搜索字符串的长度。有 O(n+m) 个算法，但它们要复杂得多。

你能告诉我们更多关于你正在搜索的数据吗？它有多大，有多冗余，搜索数组有多长，匹配错误的可能性有多大？

于 2009-11-23T00:23:39.600 回答
1

我发现以下几行更直观，但这可能是一个品味问题。

public static class ArrayExtensions
{
    public static int StartingIndex(this int[] x, int[] y)
    {
        var xIndex = 0;
        while(xIndex < x.length)
        {
            var found = xIndex;
            var yIndex = 0;
            while(yIndex < y.length && xIndex < x.length && x[xIndex] == y[yIndex])
            {
                xIndex++;
                yIndex++;
            }

            if(yIndex == y.length-1)
            {
                return found;
            }

            xIndex = found + 1;
        }

        return -1;
    }
}

此代码还解决了我认为您的实现在 x = {3, 3, 7}, y = {3, 7} 等情况下可能遇到的问题。我认为您的代码会发生什么情况是它匹配第一个数字，然后在第二个数字上重新设置，但在第三个数字上再次开始匹配，而不是在开始匹配后立即返回索引。可能会遗漏一些东西，但这绝对是需要考虑的事情，并且应该可以在您的代码中轻松修复。

于 2009-11-22T23:59:23.790 回答
0 
    //this is the best in C#

    //bool contains(array,subarray)
    //  when find (subarray[0])
    //      while subarray[next] IS OK
    //          subarray.end then Return True
    public static bool ContainSubArray<T>(T[] findIn, out int found_index,
 params T[]toFind)
    {
        found_index = -1;
        if (toFind.Length < findIn.Length)
        {

            int index = 0;
            Func<int, bool> NextOk = (i) =>
                {
                    if(index < findIn.Length-1)
                        return findIn[++index].Equals(toFind[i]);
                    return false;
                };
            //----------
            int n=0;
            for (; index < findIn.Length; index++)
            {
                if (findIn[index].Equals(toFind[0]))
                {
                    found_index=index;n=1;
                    while (n < toFind.Length && NextOk(n))
                        n++;
                }
                if (n == toFind.Length)
                {
                    return true;
                }
            }

        }
        return false;
    }
于 2013-04-03T18:39:28.953 回答
0 
using System;
using System.Linq;

public class Test
{
    public static void Main()
    {
        int[] x = {1,2,4,2,3,4,5,6};
        int[] y =       {2,3};
        int? index = null;

        for(int i=0; i<x.Length; ++i)
        {
            if (y.SequenceEqual(x.Skip(i).Take(y.Length)))
            {
                index = i;
                break;
            }
        }
        Console.WriteLine($"{index}");
    }
}

输出

3
于 2019-07-03T20:57:04.727 回答