Блог

Главная - Вопросы по программированию - C # неровный массив в список списков

C # неровный массив в список списков

#c# #list #jagged-arrays

#c# #Список #неровные массивы

Вопрос:

учитывая неровный массив:

 int[][] edges = new int[][] 
            {
                new int[] {0,1},
                new int[] {0,2},
                new int[] {0,3},
                new int[] {1,4},
            };

есть ли более элегантный способ сделать это:

 var adjlist = new List<List<int>>();
            for(int i=0; i<n; i  )
            {
                adjlist.Add(new List<int>());
            }
            
            foreach(var arr in edges)
            {
                int src = arr[0];
                int dst = arr[1];

                adjlist[src].Add(dst);
                adjlist[dst].Add(src);
            }

что-то, что улучшает временную сложность для этого, было бы идеальным.

Спасибо.

Комментарии:

1. Ничего нельзя сделать, чтобы улучшить временную сложность, поскольку она уже настолько быстра, насколько это возможно — линейное время для первого измерения ( new List<>() индексация списка и добавление элементов в список являются операциями с постоянным временем).

2. Работает ли этот код так, как вы ожидаете / хотите? потому что он выполняет довольно необычную и подозрительную операцию

3. Код работает. Это было для проблемы с кодом 261 и проходит там тесты. Чтобы преобразовать список ребер в неориентированный граф.

Ответ №1:

Я предполагаю, что код в вашем примере работает не так, как вы предполагали (возможно, я ошибаюсь). Однако преобразование неровного массива в список списков должно быть таким же простым, как следующее. Я сомневаюсь, что вы получите намного более эффективный, чем это, хотя вы могли бы провести сравнительный анализ.

Следующим является O (n), что означает, что что-то где-то должно повторяться по каждому элементу. То есть память не может быть волшебной. Сказав это, ToList вызовет List конструктор с коллекцией и будет использовать элемент экземпляра CopyTo , который, в свою очередь, использует Array.Copy и, как таковой, чрезвычайно оптимизирован для типа данных и платформы.

 var results = edges.Select(x => x.ToList()).ToList();
Метки: