Leetcode.com, задача №491 (Medium). "Возрастающие подмножества". Часть 2.

!!НАШ БЛОГ ПЕРЕЕХАЛ!!

Мы создали свой сайт! Все материалы, опубликованные в этом блоге, переехали туда.

Наш новый сайт 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).
• В массиве могут быть одинаковые числа, два одинаковых числа составляют подмножество.

Мой вариант решения показал хорошую скорость выполнения: быстрее 87% прочих вариантов. Рассмотрим самое быстрое решение.

Самый быстрый вариант решения.

Этот вариант рекурсивный. В его основе лежит функция, не возвращающая значения, FindSubsequencesBT(nums, currList, result, startIndex), где nums - входной массив, currList - рассматриваемый список, result - выходной список списков, startIndex - индекс рассматриваемого элемента массива. Входной массив просматривается не с конца, как в моём решении, а с начала.

public class Solution 
{
    public IList<IList<int>> FindSubsequences(int[] nums) 
    {
        List<IList<int>> result = new List<IList<int>>();
        List<int> currList = new List<int>();
        FindSubsequencesBT(nums, currList, result, 0);
        return result;
    }

    public void FindSubsequencesBT (int [] nums, List<int> currList, 
                                    List<IList<int>> result, int startIndex)
    {
        if(currList.Count >= 2)
            result.Add(new List<int>(currList));

        if(startIndex >= nums.Length)
            return;

        HashSet<int> visited = new HashSet<int>();
        for(int i = startIndex;i< nums.Length;i++)
        {
            if(visited.Contains(nums[i])) 
                continue;
              
            visited.Add(nums[i]);
        
            if(currList.Count == 0 || nums[i] >= currList[currList.Count-1])
            {
                currList.Add(nums[i]);
                FindSubsequencesBT (nums, currList, result, i+1);
                currList.RemoveAt(currList.Count-1);
            }
        }
    }
} 

Алгоритм функции следующий:

1. Если длина списка currList не меньше двух, то добавляем его в список списков result.
2. Если индекс startIndex элемента входного массива превышает индекс последнего элемента nums, то происходит завершение работы функции.
3. Создаётся хеш-таблица visited, в которую записываем значения элементы массива nums.
4. Далее создаётся цикл с итерациями от startIndex до последнего элемента входного массива nums.

а) если хеш-таблица содержит элемент, то переходим к следующей итерации;

б) добавляем в хеш-таблицу текущий элемент массива nums;

в) если длина списка ненулевая или элемент массива не меньше последнего элемента списка, то :

— добавляем в список элемент массива;

— запускаем функцию FindSubsequencesBT(nums, currList, result, i + 1);

— удаляем последний элемент текущего списка.

Выигрыш во времени выполнения программы происходит, полагаю, из-за того, что в итоговый список списков записываются только подходящие значения.