Разбить массив на пары

DeadLuck сказал(а):↑

Я тебе могу одну идею подкинуть, но сам решения на вскидку не найду, в студенчестве смог бы быстро найти, но сейчас уже ничего не помню.

Не рассматривал задачу с точки зрения графов? Числа это вершины, а кол-во чисел это сколько максимум ребёр может быть у данной вершины.

Нажмите, чтобы раскрыть...

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

Данил Низамов сказал(а):↑

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

Нажмите, чтобы раскрыть...

заморочно, как по мне, но даст 100% результат.

ttutiki сказал(а):↑

так в примере просто получилось, в реале не отсортирован он

так и не то у тебя. на скрине в массиве тройки три, а в результате получилось пар с тройками болльше чем три

не понимаю как тут хеш таблицы помогают, можешь подробнее расписать?

прикольно выглядит книга, может задушусь и поизучаю

Нажмите, чтобы раскрыть...

Книга это база, она просто справочник(за 9к справочник). По факту либо пиши алгоритм математически, потом юзай. Либо так, как выше предложили, в хеш и обратно в разбеение.

upd забыл добавить, какая область допустимых значений? И типо числа {a} ={a, a+1,...}

или {a} ={a.rand,a.rand,a.rand,...}. Тут могут быть проблемы.

Nubiroed сказал(а):↑

Книга это база, она просто справочник(за 9к справочник).

Нажмите, чтобы раскрыть...

да я понял, просто почитать захотелось

Nubiroed сказал(а):↑

upd забыл добавить, какая область допустимых значений? И типо числа {a} ={a, a+1,...}

или {a} ={a.rand,a.rand,a.rand,...}. Тут могут быть проблемы.

Нажмите, чтобы раскрыть...

я на таком языке не разговариваю

числа как числа, от 0 и до макс инта32

ttutiki сказал(а):↑

да я понял, просто почитать захотелось

я на таком языке не разговариваю

числа как числа, от 0 и до макс инта32

Нажмите, чтобы раскрыть...

что такое хеш таблица

https://habr.com/ru/articles/509220/

подсчет элементов(вроде то, я в метро еду, неудобно смотреть)

https://translated.turbopages.org/proxy_u/en-ru.ru.8f531424-650d986f-3e920cdd-74722d776562/https/stackoverflow.com/questions/38699817/using-python-hashmap-for-counting-elements

остается заполнить значения для хэша и сделать вывод в нужных тебе значениях

upd

книгу без математики не поймешь

Nubiroed сказал(а):↑

что такое хеш таблица

https://habr.com/ru/articles/509220/

подсчет элементов(вроде то, я в метро еду, неудобно смотреть)

https://translated.turbopages.org/proxy_u/en-ru.ru.8f531424-650d986f-3e920cdd-74722d776562/https/stackoverflow.com/questions/38699817/using-python-hashmap-for-counting-elements

остается заполнить значения для хэша и сделать вывод в нужных тебе значениях

upd

книгу без математики не поймешь

Нажмите, чтобы раскрыть...

Все равно не понял. Ну есть у нас хеш таблица с количеством каждого элемента и шо?

ttutiki сказал(а):↑

так у меня ж ответ в теме,

дописал немного чтоб понятнее было

Нажмите, чтобы раскрыть...

Спойлер

ttutiki сказал(а):↑

Все равно не понял. Ну есть у нас хеш таблица с количеством каждого элемента и шо?

Нажмите, чтобы раскрыть...

и дальше выводишь, как надо(чел тебе даже решение скинул, правда скрином)

Nubiroed сказал(а):↑

правда скрином

Нажмите, чтобы раскрыть...

это мое видение решения по этому я скинул изображением

KRATI сказал(а):↑

так у тебя массив заранее отсортирован, один проход циклом ты вычищаешь повторяющиеся элементы, второй проход собираешь пары

Спойлер

Нажмите, чтобы раскрыть...

Он имеет в виду, что число, которое уже учитывалось в паре, не может быть использовано в следующей паре

То есть после использования число удаляется из массива

Как я понял ТС хочет что-то типа такого (написал на скорую руку из потока мыслей, надо нормально переписать)

Спойлер

Ну и конечный результат вместо console.log занести в массив, но мне впадлу заново это писать

Александр сказал(а):↑

Он имеет в виду, что число, которое уже учитывалось в паре, не может быть использовано в следующей паре

То есть после использования число удаляется из массива

Как я понял ТС хочет что-то типа такого (написал на скорую руку из потока мыслей, надо нормально переписать)

Спойлер

Ну и конечный результат вместо console.log занести в массив, но мне впадлу заново это писать

Нажмите, чтобы раскрыть...

ну число может быть использовано столько сколько элементов с этим числом, я уже решил эту задачу на олимпиадном уровне непонятно зачем ты меня тегаешь со своим примитивным подходом который изменяет входной массив с использованием splice

так же тс писал что входной массив не отсортирован но это мелочи

ttutiki сказал(а):↑

так в примере просто получилось, в реале не отсортирован он

Нажмите, чтобы раскрыть...

Nubiroed сказал(а):↑

и дальше выводишь, как надо(чел тебе даже решение скинул, правда скрином)

Нажмите, чтобы раскрыть...

в смысле выводишь как надо? пар то нет

KRATI сказал(а):↑

Спойлер

Нажмите, чтобы раскрыть...

выглядит прикольно вроде. ток кажется что не во всех кейсах как будто макс пар соберет. поразбираюсь еще потом

это называется задача о максимальном паросочетании

единички соединяешь с остальными неравными элементами рёбрами

аналогично двойки с тройками и четверками

ну и т.д.

и максимальное паросочетание даст тебе ответ

но загвоздка в том, что у тебя в целом достаточно произвольный какой-то граф

вроде не двудольный точно (бывают циклы размера 3)

и надо искать парсоч в произвольном графе

короче copy paste blossom алгоритм эдмонса иполучишь O(|E| n^2)

можно ли быстрее? наверное можно

ну как минимум есть алгос за O(E sqrt(n)) но он сложный

если только два вида элементов

то за O(n) решается, но это и так понятно

а с другой стороны у тебя не такой уж рандомный граф: дополнение набора полно-связных графов

в теории можно подумать о том, можно ли там как-то эту специфику использовать

но я не хочу ща это делать

в общем в эту сторону смотри

во всяком случае я предложил точно корректное решение, но говеное

я не знаю зачем тебе разбивать на пары, но наверное это не та задача, где приемлемо O(n^4) и даже O(n^(2 + 1/2))

KRATI сказал(а):↑

ну число может быть использовано столько сколько элементов с этим числом

Нажмите, чтобы раскрыть...

&

ttutiki сказал(а):↑

Нужно разбить на пары, где каждая пара состоит из уникальных элементов с разными значениями. Каждый элемент может использоваться только в одной паре!

Нажмите, чтобы раскрыть...

ttutiki сказал(а):↑

P.S.в одном из пробных моих вариантов нужно было узнать максимальное количество пар, но че то не смог. Пришлось отказаться от варианта. Интересно будет если кто-то разжует можно тут по массиву с помощью какой нибудь формулы прикольной это узнать или нельзя.

Как обычно, в математике 0.

Нажмите, чтобы раскрыть...

Пусть n - количество чисел в массиве. Если n - нечетное, то оставляем без пары самое "популярное*" число в массиве, удаляем его из массива и уменьшаем размер массива на 1.

Пусть k - сколько раз самое "популярное" число встречается в измененном массиве. Рассмотрим два случая:

1. k ≥ n - k (количество "популярного" числа больше или равно количества всех остальных чисел).
   В этом случае мы будем собирать в пары "популярное" число с не популярным. Таким образом, соберем (n-k) пар.
   
   
2. k < n - k (количество "популярного" числа меньше количества всех остальных чисел).
   В этом случае мы сможем собрать все пары (n / 2). Чтобы это сделать, можно, например, собирать пары чисел, которых больше всего в массиве. Заметим, что у нас сохраняется на каждом шаге правило, что "популярное" число меньше, чем все остальные. Если мы вдруг не сможем взять никакое из оставшихся чисел, то значит у нас в какой-то момент времени осталась кучка из хотя бы 2 "популярных" чисел, что больше, чем количество остальных. Противоречие. Значит, мы сможем брать числа пока они не кончатся, и, получается, что ответ - половина всех чисел.

*Популярным я назвал число, которые встречается чаще других в массиве.

у чатгпт спроси, он такое хорошо решает, даже отдебажит тебе поэтапно

HaisTous сказал(а):↑

Пусть n - количество чисел в массиве. Если n - нечетное, то оставляем без пары самое "популярное*" число в массиве, удаляем его из массива и уменьшаем размер массива на 1.

Пусть k - сколько раз самое "популярное" число встречается в измененном массиве. Рассмотрим два случая:

1. k ≥ n - k (количество "популярного" числа больше или равно количества всех остальных чисел).
   В этом случае мы будем собирать в пары "популярное" число с не популярным. Таким образом, соберем (n-k) пар.
   
   
2. k < n - k (количество "популярного" числа меньше количества всех остальных чисел).
   В этом случае мы сможем собрать все пары (n / 2). Чтобы это сделать, можно, например, собирать пары чисел, которых больше всего в массиве. Заметим, что у нас сохраняется на каждом шаге правило, что "популярное" число меньше, чем все остальные. Если мы вдруг не сможем взять никакое из оставшихся чисел, то значит у нас в какой-то момент времени осталась кучка из хотя бы 2 "популярных" чисел, что больше, чем количество остальных. Противоречие. Значит, мы сможем брать числа пока они не кончатся, и, получается, что ответ - половина всех чисел.

*Популярным я назвал число, которые встречается чаще других в массиве.

Нажмите, чтобы раскрыть...

k < n - k инвариант не сохраняется

11133355

113355

1355 (ой)

---

надо хотя бы k <= n - k

и изымать пару надо из больших групп

---

тогда вроде после вынесения пары

веса изменятся так

k_i’ = k_i - 1

k_j’ = k_j - 1

n’ = n - 2

k_z’ = k_z

для k_i, k_j всё замечательно, инвариант сохраняется

не понятно что с остальными группами

---

Лемма: дляk_z всегда выполнено 2*(k_z + 1) <= n

ну в самом деле заметим, что n >= 4

для двух просто нет никаких третьих групп утверждение само собой выполнилось

допустим k_i <= k_j <= k_z

где z это все кроме i, j

рассмотрим случай k_i = 1

так как k_i — максимум, то и так всё очевидно 2*(k_z + 1) <= 4 <= n

но тогда в оставшихся случаях: k_i >= 2

k_i + k_z + k_j <= sum(k_t) = n

k_i + 2 * k_z <= n

2(k_z + 1) <= n

---

ну и всё:

по лемме у нас всегда выполнен инвариант

k_t <= n - k_t

когда мы извлекаем пару из двух самых больших групп

---

алгос тогда за n log n в тупую

точно делается любым деревом поиска

или даже кучей можно, еще тупее:

извлекаешь 2 максимума (массивы с ключом их размера)

достаешь пару, возвращаешь их на место

прикольно кстати, максимальный парсоч для графов дополнений за O(n log n) решился, это весьма шустро

YoshkinKot сказал(а):↑

k < n - k инвариант не сохраняется

11133355

113355

1355 (ой)

---

надо хотя бы k <= n - k

и изымать пару надо из больших групп

---

тогда вроде после вынесения пары

веса изменятся так

k_i’ = k_i - 1

k_j’ = k_j - 1

n’ = n - 2

k_z’ = k_z

для k_i, k_j всё замечательно, инвариант сохраняется

не понятно что с остальными группами

---

Лемма: дляk_z всегда выполнено 2*(k_z + 1) <= n

ну в самом деле заметим, что n >= 4

для двух просто нет никаких третьих групп утверждение само собой выполнилось

допустим k_i <= k_j <= k_z

где z это все кроме i, j

рассмотрим случай k_i = 1

так как k_i — максимум, то и так всё очевидно 2*(k_z + 1) <= 4 <= n

но тогда в оставшихся случаях: k_i >= 2

k_i + k_z + k_j <= sum(k_t) = n

k_i + 2 * k_z <= n

2(k_z + 1) <= n

---

ну и всё:

по лемме у нас всегда выполнен инвариант

k_t <= n - k_t

когда мы извлекаем пару из двух самых больших групп

---

алгос тогда за n log n в тупую

точно делается любым деревом поиска

или даже кучей можно, еще тупее:

извлекаешь 2 максимума (массивы с ключом их размера)

достаешь пару, возвращаешь их на место

прикольно кстати, максимальный парсоч для графов дополнений за O(n log n) решился, это весьма шустро

Нажмите, чтобы раскрыть...

Я имел ввиду, что на итоговое количество пар знак равенства влиять не будет, так как если k=n-k, то можно выводить либо n/2, либо n-k.

А для доказательства второго случая действительно нужно использовать нестрогое неравенство.