Помогите решить задачу с массивами в C#

117

23 июня 2021, 14:00

Суть задачи в чем, имеется два строковых массива. Допустим массив "А" и "В". Массив А содержит в себе название доменов сайтов, пример:

string[] А = { "unlock.microvirus.md", "visitwar.com", "visitwar.de", "fruonline.co.uk", "australia.open.com", "credit.card.us"};

Массив В тоже содержит в себе названия доменов, но тех которые должны быть заблокированы, пример:

string[] B = { "microvirus.md", "visitwar.de", "piratebay.co.uk", "list.stolen.credit.card.us" };

Необходимо Написать функцию (в C #):

class Solution 
{
    public static int [] solution (string [] A, string [] B); 
}

что, учитывая непустой массив A из N доменов, возвращает последовательность, состоящую из L целых чисел, где каждое целое число представляет N-индекс домена во входном массиве A, который не заблокирован.

Ниже приведен мой код, как я это сделал, но мне говорят, что это не оптимально по скорости. Простой перебор по массиву В тоже не вариант. Какие ещё есть варианты?

public static int[] solution(string[] A, string[] B)
    {
        string[] UnBlockedDomains = A;
        foreach(var blocked in B)
        {
            UnBlockedDomains = (from x in UnBlockedDomains where !x.Contains(blocked) select x).ToArray();
        }
        int[] IdDomainsUnBlocked = new int[UnBlockedDomains.Length];
        int i = 0;
        foreach(var domain in UnBlockedDomains)
        {
            IdDomainsUnBlocked[i++] = Array.IndexOf(A, domain);
        }
        return IdDomainsUnBlocked;
    }

Answer 1

Т.к. для каждого элемента в А используется поиск элемента в В - лучше перевести В в HashSet<string> ради O(1) поиска

static int[] solution(string[] A, string[] B)
{
   var blockedSet = new HashSet<string>(B);
   var result = new List<int>();
   for (var i = 0; i < A.Length; i++)
   {
       if (!blockedSet.Contains(A[i])) result.Add(i);
   }
   return result.ToArray();
}

Answer 2

Можно сделать выражением Linq:

using System;
using System.Linq;
using System.Collections.Generic;
public class Test
{
    static readonly string[] ListA =
    {
        "unlock.microvirus.md",
        "visitwar.com",
        "visitwar.de",
        "fruonline.co.uk",
        "australia.open.com",
        "credit.card.us"
    };
    static readonly string[] ListB =
    {
        "microvirus.md",
        "visitwar.de",
        "piratebay.co.uk",
        "list.stolen.credit.card.us"
    };
    public static void Main()
    {
        IEnumerable<int> result = ListA
            // провоцируем в новую форму последовательность анонимного
            // типа 'a{ int Index { get; } string Value { get; } }
            .Select((o, i) => new
            {
                Index = i,
                Value = o
            })
            // выполняем фильтрацию
            .Where(o => ListB.Contains(o.Value))
            // выбираем индексы `'a.Index`, откидывая значения
            .Select(o => o.Index);

        foreach(int i in result)
        {
            Console.WriteLine("index at: {0}", i);
        }
        Console.ReadKey(true);
    }
}

Вывод: