Задание по c#, time limit

Question

выполнял задание по c#, у меня вроде всё нормально, но при проверке уже на сайте через некоторое время происходит ошибка time limit

Само задание: Даны два массива целых чисел. Напишите программу, которая найдет все числа, которые есть во втором массиве, но отсутствуют в первом.

В первой строке даны два числа n и m — длины первого и второго массива. Во второй строке содержатся n чисел для первого массива. В третьей строке содержатся m чисел для второго массива.

Сам код:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Collections;
using System.IO;

namespace Tasks
{
    public class Program
    {
        public static void Main(string[] args)
        {
            var n = Console.ReadLine().Split(' ');  //Длины двух массивов

            var nums = Console.ReadLine().Split(' ');   //Первый массив
            var nums1 = Console.ReadLine().Split(' ');  //Второй массив

            var count = 0;  //Счетчик

            var globalNums = new List<string>();    //Значения, которые встречаются во втором, но не встречаюся в первом массиве

            for (var i = 0; i < nums1.Length; i++)
            {
                if (!nums.Contains(nums1[i]))
                {
                    globalNums.Add(nums1[i]);
                    count++;
                }
            }

            Console.WriteLine(count);   //Вывод счётчика на экран

            foreach (var item in globalNums)    //Вывод массива на экран
            {
                Console.Write(item + " ");
            }
        }
    }
}

Ошибка

Описание ошибки

Answer 1

Верно написано

Задача может быть решена за O(nlogn) без доп. памяти или за линейное время с использованием дополнительной памяти.

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

Вот тот же алгоритм:

static void Main(string[] args)
{
    Console.ReadLine(); // длины не используются, следовательно нет смысла их парсить
    int[] nums = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
    int[] nums1 = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();

    List<int> globalNums = new List<int>();

    for (int i = 0; i < nums1.Length; i++)
    {
        if (Array.IndexOf(nums, nums1[i]) == -1)
        {
            globalNums.Add(nums1[i]);
        }
    }

    Console.WriteLine(globalNums.Count);
    Console.WriteLine(string.Join(' ', globalNums));
}

Пройдет ли он тестирование - не знаю, но отработает значительно быстрее.

Далее, можно оптимизировать поиск и сложность алгоритма с помощью HashSet

static void Main(string[] args)
{
    Console.ReadLine(); // длины не используются, следовательно нет смысла их парсить
    HashSet<int> nums = Console.ReadLine().Split(' ').Select(int.Parse).ToHashSet();
    int[] nums1 = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();

    List<int> globalNums = new List<int>(nums1);

    for (int i = 0; i < nums1.Length; i++)
    {
        int x = nums1[i];
        if (!nums.Contains(x))
        {
            globalNums.Add(x);
        }
    }

    Console.WriteLine(globalNums.Count);
    Console.WriteLine(string.Join(' ', globalNums));
}

Прикол HashSet<T> в том, что при этом необязательно парсить в числа, так как строки сами по себе не будут сравниваться, будут сравниваться только их хэши. А хэш в данном конкретном случае будет высчитываться из каждой строки только однажды.

Получается вот так

static void Main(string[] args)
{
    Console.ReadLine(); // длины не используются, следовательно нет смысла их парсить
    HashSet<string> nums = new HashSet<string>(Console.ReadLine().Split(' '));
    string[] nums1 = Console.ReadLine().Split(' ');

    List<string> globalNums = new List<string>();

    for (int i = 0; i < nums1.Length; i++)
    {
        string x = nums1[i];
        if (!nums.Contains(x))
        {
            globalNums.Add(x);
        }
    }

    Console.WriteLine(globalNums.Count);
    Console.WriteLine(string.Join(' ', globalNums));
}

БЛОГ НА HUSL

Задание по c#, time limit

Ответы (1 шт):