Leetcode.com, задача №491 (Medium). "Возрастающие подмножества". Часть 1.
!!НАШ БЛОГ ПЕРЕЕХАЛ!!
Мы создали свой сайт! Все материалы, опубликованные в этом блоге, переехали туда.
Наш новый сайт maddevelop.ru
А данную статью вы можете найти по ссылке
Условие
Дан массив типа int. Необходимо найти в нём все различные возрастающие подмножества длиной не меньше 2.
Пример
Входной массив: { 4, 6, 7, 7 }
Выходные подмножества: { 4, 6 }, { 4, 7 }, { 4, 6, 7 }, {4, 6, 7, 7}, { 6, 7 }, { 6, 7, 7}, {7, 7}, { 4, 7, 7}
Уточнения:
- Длина массива не превышает 15 элементов.
- Значения чисел массива лежат в интервале (-100, 100).
- В массиве могут быть одинаковые числа, два одинаковых числа составляют подмножество.
Мой вариант решения
Для начала подумаем, о чём говорят уточнения к задаче.
Из первого следует, что прямой перебор будет крайне ресурсоёмким, ведь число возможных вариантов равняется (n! + 1), где n - длина входного массива. 15! = 1 307 674 368 000 - гигантское число, поэтому прямой перебор следует отложить.
Причина появления второго условия осталась непонятой, ведь числа входного массива являются числами типа int. Быть может, для ускорения вычислений и уменьшения используемой памяти следует сделать сужающее преобразование типа...
Третье условие сообщает нам о том, что подмножества на самом деле должны быть неубывающими. Именно оно принесло много хлопот во время решения.
Приведём сразу код решения, а потом пошагово его разберём:
public static IList<IList<int>> FindSubsequences(int[] nums)
{
IList<IList<int>> answear = new List<IList<int>>();
if (nums.Length < 2)
return answear;
Dictionary<int, int> dict = new Dictionary<int, int>();
bool povtor;
int count = 0;
for (int i = 0; i < nums.Length; i++)
{
count = answear.Count;
povtor = dict.ContainsKey(nums[i]);
if (!povtor)
{
answear.Add(new int[] { nums[i] }.ToList());
dict.Add(nums[i], count);
}
for (int j = 0; j < count; j++)
{
if (povtor)
{
if ((j >= dict[nums[i]]) && (answear[j].Last() <= nums[i]))
{
List<int> helped = answear[j].Select(y => y).ToList();
helped.Add(nums[i]);
answear.Add(helped);
}
}
else
{
if (answear[j].Last() <= nums[i])
{
List<int> helped = answear[j].Select(y => y).ToList();
helped.Add(nums[i]);
answear.Add(helped);
}
}
}
if (povtor)
dict[nums[i]] = count;
}
for (int i = 0; i < answear.Count;)
{
if (answear[i].Count == 1)
answear.RemoveAt(i);
else
i++;
}
return answear;
}
В начале инициализируем список списков answear, который и будет содержать выходные подмножества. Словарь dict предназначен для хранения элементов входного массива и индекс их первого появления в answear. Флаг povtor указывает, был ли ранее исследован элемент из входного массива nums. Переменная count показывает текущую длину списка answear.
IList<IList<int>> answear = new List<IList<int>>(); if (nums.Length < 2) return answear; Dictionary<int, int> dict = new Dictionary<int, int>(); bool povtor; int count = 0;
Далее мы последовательно начинаем перебирать элементы из входного массива. В начале каждой итерации определяем count и является ли текущий элемент повторным. Для второго достаточно просмотреть ключи в dict.
count = answear.Count; povtor = dict.ContainsKey(nums[i]);
Если элемент ранее не исследовался, то мы помещаем его в список и добавляем в конец answear. Также заносим nums[i] в словарь. Сам элемент является ключом, а значением - его индекс в answear, равный count.
if (!povtor)
{
answear.Add(new int[] { nums[i] }.ToList());
dict.Add(nums[i], count);
}
После этого начинаем перебирать все списки в answear.
for (int j = 0; j < count; j++)
{
.....
Затем обработка списков разделяется на две ветви в зависимости от значения переменной povtor.
Если значение i-го элемента входного массива обрабатывалось, то проверяем, индекс текущего списка больше ли последнего индекса текущего рассматриваемого элемента массива (j >= dict[nums[i]]), а также превышает (или равняется)элемент массива последнее число рассматриваемого списка (answear[j].Last() <= nums[i]).
При выполнении всех условий создаём копию текущего списка, записываем в её конец текущий элемент массива и добавляем созданный таким образом список в answear.
if (povtor)
{
if ((j >= dict[nums[i]]) && (answear[j].Last() <= nums[i]))
{
List<int> helped = answear[j].Select(y => y).ToList();
helped.Add(nums[i]);
answear.Add(helped);
}
}
Если второе условие второго оператора if требуется для создания неубывающего подмножества, то для чего же первое условие?
Рассмотрим простой массив {1, 2, 1, 1}.
Первая итерация
answear = { 1 };
Вторая итерация
answear = { 1 }, { 2 }, {1, 2}
Третья итерация
answear = { 1 }, { 2 }, { 1, 2 }, { 1 }, { 1, 1 }
Четвёртая итерация
answear = { 1 }, { 2 }, { 1, 2 }, { 1 }, { 1, 1 }, { 1 }, { 1, 1 }, { 1, 1, 1 }
Видно, что после четвёртой итерации появился повтор списка { 1, 1 }. Повторы в дальнейшем очень накладно удалять из answear. Поэтому используется dict - словарь с индексами последних появлений элементов во входном массиве.
Если же элемент ранее не появлялся в массиве, то мы сравниваем его с последним числом в предыдущих списках и при верном равенстве добавляем элемент в конец списков. Так как код повторяется в обоих условиях оператора if, то можно создать метод типа void.
if (povtor)
{
.....
}
else
{
if (answear[j].Last() <= nums[i])
{
List<int> helped = answear[j].Select(y => y).ToList();
helped.Add(nums[i]);
answear.Add(helped);
}
}
После прохода по всем предыдущим спискам, если элемент повторный, обновляем индекс в словаре dict.
if (povtor)
dict[nums[i]] = count;
В самом конце удаляем списки, состоящие из одного элемента, и выводим answear в качестве ответа.
for (int i = 0; i < answear.Count;)
{
if (answear[i].Count == 1)
answear.RemoveAt(i);
else
i++;
}
Оценим сложности выполнения алгоритма.
В худшем случае (при возрастающем входном массиве) временная сложность останется равной n!. Но при невозрастающем массиве затратные по времени и памяти операции по созданию списков могут заменяться на простые операции сравнения индексов элементов.
Пространственная сложность: n, так как используется дополнительный словарь последних индексов.
Ещё больше интересной информации на нашем Telegram канале.