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

Дан массив arr[] , состоящий из N целых чисел, задача состоит в том, чтобы разбить массив на два подмножества так, чтобы количество уникальных элементов в обоих подмножествах было одинаковым, и для каждого элемента выведите 1 , если этот элемент принадлежит первому подмножеству. . В противном случае выведите 2 . Если сделать такой раздел невозможно, то выведите «-1» .

Примеры:

Input: arr[] = {1, 1, 2, 3, 4, 4}
Output: 1 1 1 2 1 1
Explanation: Consider the first and the second subset of the partition of the array as {1, 1, 2, 4 4} and {3}. Now, the above partition of subsets has equal count of distinct elements..

Input: arr[] = {1, 1, 2, 2, 3}
Output: -1

Наивный подход: данная проблема может быть решена путем создания всех возможных разделов элементов массива на два подмножества, и если существует какой-либо такой раздел, количество различных элементов которого одинаково, то выведите 1 и 2 в соответствии с принадлежностью соответствующих элементов массива. к. В противном случае выведите «-1» , так как такого возможного раздела массива не существует.

Временная сложность: O(N* ^2N )
Вспомогательное пространство: O(N)

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

• Инициализируйте карту, скажем, M , чтобы сохранить частоту всех элементов массива.
• Инициализируйте массив, скажем, ans[] , в котором хранится номер подмножества, которому принадлежит каждый элемент массива.
• Найдите количество уникальных элементов в массиве, подсчитав элемент, имеющий частоту 1 на карте M . Пусть этот счет будет C .
• Если значение C четное, то переместите половину этих элементов в первое подмножество, пометив эти элементы как 1 , а остальные элементы как 2 в массиве ans[] .
• В противном случае проверьте, существует ли какой-либо элемент с частотой больше 2 , а затем переместите один экземпляр этого элемента во второе подмножество. В противном случае выведите «-1» .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N)
Вспомогательное пространство: O(1)