时间戳

首页 > 解决方案 > 查找多个Array中匹配元素的所有索引

c# - 查找多个Array中匹配元素的所有索引

问题描述

假设我有两个数组如下

int[] first = { 1, 2, 3, 4, 5, 6, 12, 13, 14 };
int[] second = { 12, 13, 14, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9 };

我想要的结果如下：

matching index from the first = 6,7,8 
matching index from second = 0,1,2

条件：我无法对数组进行排序以找到索引，并且可以有任意数量的数组。

我正在寻找一些有效的解决方案，我会很高兴得到帮助。提前致谢。

下面是我为这两个数组所做的代码：

class Program
{
    static void Main(string[] args)
    {
        int[] first = { 1, 2, 3, 4, 5, 6, 12, 13, 14 };
        int[] second = { 12, 13, 14, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9 };
        IndexArray sameIndexArray = CompareArray(first, second);
        Console.WriteLine("FOLLOWING ARE THE INDEX WITH SAME VALUE FOR FIRST ARRAY");
        foreach (var index in sameIndexArray.FirstArray)
        {
            Console.WriteLine(index);
        }
        Console.WriteLine("FOLLOWING ARE THE INDEX WITH SAME VALUE FOR SECOND ARRAY");
        foreach (var index in sameIndexArray.SecondArray)
        {
            Console.WriteLine(index);
        }

        Console.ReadKey();
    }

    private static IndexArray CompareArray(int[] firstArray, int[] secondArray)
    {
        IndexArray arrayIndex = new IndexArray();
        arrayIndex.FirstArray = new List<int>();
        arrayIndex.SecondArray = new List<int>();
        for (int i = 0; i < firstArray.Length; i++)
        {
            for (int j = 0; j < secondArray.Length; j++)
            {
                if (firstArray[i] == secondArray[j])
                {
                    arrayIndex.FirstArray.Add(i);
                    arrayIndex.SecondArray.Add(j);
                }
            }
        }

        return arrayIndex;
    }
}

public class IndexArray
{
    public List<int> FirstArray { get; set; }
    public List<int> SecondArray { get; set; }
}

标签： c#arrays

解决方案

您的解决方案是 O(N^2)。O(N) 或 O(N log N) 解决方案应该是可能的：

  • 为每个集合创建一个 HashSet
  • 遍历第一组，通过 hashset2.Contains 过滤并打印索引
  • 反之亦然

像这样的东西：

private static IndexArray CompareArray(int[] firstArray, int[] secondArray)
{
    IndexArray arrayIndex = new IndexArray();
    var hashset2 = new HashSet<int>(secondArray);
    for (int i = 0; i < firstArray.Length; i++)
    {
        if (hashset2.Contains(firstArray[i]))
            arrayIndex.FirstArray.Add(i);
    }
    var hashset1 = new HashSet<int>(firstArray);
    for (int i = 0; i < secondArray.Length; i++)
    {
        if (hashset1.Contains(secondArray[i]))
            arrayIndex.SecondArray.Add(i);
    }

    return arrayIndex;
}

推荐阅读