|
Труд вопреки насмешкам
|
|
Создать список фрагментов данного списка22.03.2019, 19:47. Показов 1791. Ответов 9
Метки нет (Все метки)
Допустим, есть список целых чисел, например, { 1, 2, 3, 2, 3, 4, 5, 4, 5, 6, 4, 7, 1, 8, 8, 9, 8 }. Нужно создать список фрагментов этого списка по следующим правилам (постараюсь описать правила максимально "вменяемо", чтобы потом не было претензий):
1. Длина списка фрагментов равна длине исходного списка, каждый фрагмент номер i начинается с элемента исходного списка номер i. 2. Если данный элемент единственный (встречается один раз) в исходном списке, он единственный во фрагменте. 3. Если в исходном списке несколько одинаковых элементов, сравниваются следующие за каждым из них, если они также одинаковые, еще следующие и т. д. (следующим за последним считается первый). 4. Фрагмент имеет минимально возможную длину из элементов, следующих подряд за i, такую, чтобы все фрагменты были уникальными. 5. Затраты времени - не больше O(m * n * log(n)), памяти - не больше O(m * n), где m - максимальная длина фрагмента. Например, из вышеупомянутого списка получится вот что: { { 1, 2 }, { 2, 3, 2 }, { 3, 2 }, { 2, 3, 4 }, { 3, 4 }, { 4, 5, 4 }, { 5, 4 }, { 4, 5, 6 }, { 5, 6 }, { 6 }, { 4, 7 }, { 7 }, {1, 8 }, { 8, 8 }, { 8, 9 }, { 9 }, { 8, 1 } }. Пояснения: { 6 }, { 7 }, { 9 } - эти элементы в списке единственные, поэтому в их фрагменты уже ничего не нужно добавлять. { 3, 2 }, { 3, 4 } - тройки общие, а 2 и 4 отличаются, поэтому фрагмент состоит из двух элементов. { 2, 3, 2 }, { 2, 3, 4 } - тут два элемента общие, поэтому для уникальности фрагмента требуется третий. { 4, 5, 4 }, { 4, 5, 6 }, { 4, 7 } - семерка отличается от обеих пятерок, поэтому третий элемент не нужен, а вот пятерки совпадают, поэтому нужен третий элемент. { 8, 8 } - фрагмент может состоять и из одинаковых элементов. { 8, 1 } - за последним элементом списка следует первый. Linq допускается и даже приветствуется. Возможно ли это? Добавлено через 16 минут Мне вот интересно, почему все видят мою тему и проходят мимо? Я же спросил: "Возможно ли это?" - если невозможно, так и напишите, и объясните, почему. Или я опять невнятно сформулировал вопрос? Тогда попросите уточнить. Но просто ноль реакции - это бесит меня. Я же не тролль какой-нибудь, которого все стремятся игнорировать...
0
|
|
| 22.03.2019, 19:47 | |
|
Ответы с готовыми решениями:
9
Как создать “Список списка” из данного задания?
|
|
Труд вопреки насмешкам
|
|
| 23.03.2019, 11:18 [ТС] | |
|
Ну, что напишете? У вас жизненная позиция такая - игнорировать именно меня? Чем я вам не угодил? Причем ВСЕМ?! Можете ответить прямо, а не томить молчанием?
0
|
|
|
384 / 184 / 107
Регистрация: 07.01.2016
Сообщений: 496
|
||||||||||||
| 23.03.2019, 17:31 | ||||||||||||
|
Etyuhibosecyu,
служебные классы: Кликните здесь для просмотра всего текста
Метод, возвращающий массив списков исходя из начального списка
1
|
||||||||||||
|
Труд вопреки насмешкам
|
|
| 23.03.2019, 17:44 [ТС] | |
|
alexus5, спасибо за ответ. Ваш код, мягко говоря, впечатляет. Но ЧЕТЫРЕ вложенных цикла - это время выполнения явно не O(m * n * log(n)).
Добавлено через 42 секунды Хотя попробую применить и посмотрю на время выполнения.
0
|
|
|
384 / 184 / 107
Регистрация: 07.01.2016
Сообщений: 496
|
|||||||||||
| 23.03.2019, 19:09 | |||||||||||
Сообщение было отмечено Etyuhibosecyu как решение
Решение
Etyuhibosecyu, вот вариант по-проще
служебный класс: Кликните здесь для просмотра всего текста
и метод
1
|
|||||||||||
|
Труд вопреки насмешкам
|
||
| 23.03.2019, 19:15 [ТС] | ||
|
Добавлено через 3 минуты alexus5, похоже, первый вариант действительно имеет именно такую сложность. Типичный список длиной 30000 обрабатывает за 8-12 секунд, а если много похожих фрагментов - за 2-3 минуты.
0
|
||
|
384 / 184 / 107
Регистрация: 07.01.2016
Сообщений: 496
|
|
| 23.03.2019, 19:19 | |
|
0
|
|
|
384 / 184 / 107
Регистрация: 07.01.2016
Сообщений: 496
|
|
| 23.03.2019, 19:40 | |
|
Etyuhibosecyu, у второго линейно относительно размера входного списка. у первого экспоненциально)
0
|
|
|
Труд вопреки насмешкам
|
||
| 23.03.2019, 19:41 [ТС] | ||
|
alexus5, у меня ругается на эту строку:
0
|
||
| 28.03.2019, 09:17 | |
|
Не по теме: Самое время новый язык начать изобретать, где таких ошибок не будет.
0
|
|
| 28.03.2019, 09:17 | |
|
Помогаю со студенческими работами здесь
10
Функция, возвращающая список состоящий из элементов данного списка + n последних элементов списка Новый список из n элементов данного списка List.map (на основе данного списка получить новый список) Из данного одноуровнего списка построить список списков его элементов
Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
AkelPad-скрипты, структуры, и немного лирики..
testuser2 05.04.2026
Такая программа, как AkelPad существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .
|
Отображение реквизитов в документе по условию и контроль их заполнения
Maks 04.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеСпецтехники", разработанного в конфигурации КА2.
Данный документ берёт данные из другого нетипового документа. . .
|
Фото всей Земли с борта корабля Orion миссии Artemis II
kumehtar 04.04.2026
Это первое подобное фото сделанное человеком за 50 лет. Снимок называют новым вариантом легендарной фотографии «The Blue Marble» 1972 года, сделанной с борта корабля «Аполлон-17». Новое фото. . .
|
Вывод диалогового окна перед закрытием, если документ не проведён
Maks 04.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2.
Задача: реализовать программный контроль на предмет проведения документа. . .
|
|
Программный контроль заполнения реквизитов табличной части документа
Maks 02.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2.
Задача:
1. Реализовать контроль заполнения реквизита. . .
|
wmic не является внутренней или внешней командой
Maks 02.04.2026
Решение:
DISM / Online / Add-Capability / CapabilityName:WMIC~~~~
Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/
|
Программная установка даты и запрет ее изменения
Maks 02.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2.
Задача: при создании документов установить период списания автоматически. . .
|
Вывод данных в справочнике через динамический список
Maks 01.04.2026
Реализация из решения ниже выполнена на примере нетипового справочника "Спецтехника" разработанного в конфигурации КА2.
Задача: вывести данные из ТЧ нетипового документа. . .
|