在 C# 中查找子数组的第一次出现/起始索引 [英] Find the first occurrence/starting index of the sub-array in C#

问题描述

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

Given two arrays as parameters (x and y) and find the starting index where the first occurrence of y in x. I am wondering what the simplest or the fastest implementation would be.

示例:

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

更新:由于我的代码有误，我将其从问题中删除.

Update: Since my code is wrong I removed it from the question.

推荐答案

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

Here is a simple (yet fairly efficient) implementation that finds all occurances of the array, not just the first one:

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 数组仅包含完整匹配项.

The method first loops through the x array to find all occurances of the first item in the y array, and place the index of those in the index array. Then it goes on to reduce the matches by checking which of those also match the second item in the y array. When all items in the y array is checked, the index array contains only the full matches.

另一种实现是从循环中的语句中删除 ToArray 调用，使其仅:

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

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

This would totally change how the method works. Instead of looping through the items level by level, it would return an enumerator with nested expressions, deferring the search to the time when the enumerator was iterated. That means that you could get only the first match if you wanted:

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

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

This would not find all matches and then return the first, it would just search until the first was found and then return it.

这篇关于在 C# 中查找子数组的第一次出现/起始索引的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！