Учитывая кучу целых чисел, выведите всю комбинацию всех возможных чисел, используя только операцию плюса
Учитывая кучу целых чисел, выведите всю комбинацию всех возможных чисел, используя только операцию «плюс».
Например,
[10, 20] => [10, 20, 30]
[1, 2, 3] => [1, 2, 3, 4, 5, 6]
[10, 20, 20, 50] => [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
Может ли кто-нибудь помочь мне с методом сделать это на Java?
Я сделал попытки, и я думаю, что это работает, но ищу другие решения.
public int[] getCoins2(int[] coins) {
Set<Integer> result = new TreeSet<>();
for (int coin : coins) {
result.addAll(result.stream().map(value -> value + coin).collect(Collectors.toSet()));
result.add(coin);
}
return toInt(result);
}
public int[] toInt(Set<Integer> set) {
int[] a = new int[set.size()];
int i = 0;
for (Integer val : set) {
a[i++] = val;
}
return a;
}
public static void main(String[] args) {
CoinCombination combination = new CoinCombination();
int[] coins = {10, 20, 20, 50, 100};
System.out.println(Arrays.toString(combination.getCoins2(coins)));
}
Подсказка: начните с алгоритма пузырьковой сортировки, но на самом деле не сортируйте список. Скорее поместите сумму элементов в хеш-набор
Что значит "думаю, что это работает"? У вас есть модульные тесты?
Не знаю, как работает ОП. Я давно не задавал вопросов
У меня был модульный тест, но я не могу охватить все случаи
Хорошо, затем покажите те, которые не работают, и результат, который вы получаете ... Кроме того, пошаговое выполнение с помощью отладчика может помочь
Не имеет значения, отсортирован исходный массив или нет, это не повлияет на результат.
У меня нет ни одного неудачного, я имею в виду, что все мои тестовые примеры прошли от массива размера 1 до массива размера 5
Я специально сказал не сортировать список, скорее я имел в виду начать с вложенного цикла for по значениям
Позвольте нам продолжить обсуждение в чате.
«Искать другие решения» - не очень хороший вопрос.
Связанный: Вернуть все возможные суммы, которые можно сформировать с помощью чисел в массиве JAVA.. Ищите больше.
Я бы выбрал рекурсивный метод для генерации комбинаций и TreeSet для хранения результатов для отсортированного вывода.
Когда вы говорите «все возможные суммы», вы также имеете в виду суммы подпоследовательностей?
Если в вашем массиве 5 чисел, то каждое число может быть включено или не включено в сумму. Это аккуратно отображается на 5 двоичных битов. Сгенерируйте все двоичные числа от b00000 до b11111. Подсчитайте суммы всех чисел, отмеченных цифрой 1. Удалите повторяющиеся результаты, и вы решили проблему.
@ vivek_23 да, вы можете использовать только одно число, два или все, чтобы суммировать и получить новый результат.
@ OleV.V. Спасибо, я проверил, но выяснил, что мне сложно понять версию рекурсии :(
Предполагая, что ваш итеративный код выполняет свою работу, вам не о чем беспокоиться. Рекурсию сначала сложно понять, это отличный инструмент, когда вы овладеете им (наконец-то).
Хорошо, я продолжу изучать рекурсию подробнее
Ответы 1
Как вы упомянули в своем заявлении о проблеме:
please output all combination of all possible numbers by using plus operation only.
Временная сложность решения останется экспоненциальной, то есть О (2N-1), поскольку мы должны проверять каждую подпоследовательность массива.
Поскольку вы используете TreeSet, сложность
addдобавит накладные расходы log (n), а addAll () добавит сложностьO(m log (n))в худшем случае, гдеmиn- количество элементов в каждом дереве. См. Этот отвечать.С технической точки зрения, сложность на каждом шаге составит O (m log (n)), что составит O (2N - 1) * O (m log (n)).
Я предлагаю вам лучше использовать HashSet, где
add()иcontains()в среднем дадут вам производительность O (1) (может подняться до O (n), если есть коллизии, но обычно это не так).Таким образом, сложность остается O (2N-1) с накладными расходами
additional(не мультипликативными) в конце (если вы используетеwishдля сортировки), которым будетO(m log m), гдеm~ 2N - 1. Вы можете сравнить время выполнения оба подхода тоже.
Код:
import java.util.*;
public class CoinCombination {
public List<Integer> getCoinSums(int[] coins) {
Set<Integer> set = new HashSet<>();
List<Integer> sums = new ArrayList<>();
for (int coin : coins) {
int size = sums.size();
for(int j=0;j<size;++j){
int new_sum = sums.get(j) + coin;
if (!set.contains(new_sum)){
sums.add(new_sum);
set.add(new_sum);
}
}
if (!set.contains(coin)){
sums.add(coin);
set.add(coin);
}
}
Collections.sort(sums);
return sums;
}
public static void main(String[] args) {
CoinCombination combination = new CoinCombination();
int[][] coins = {
{10,20},
{1,2,3},
{10, 20, 20, 50},
{10, 20, 20, 50, 100}
};
for(int[] each_set_of_coins : coins){
System.out.println(combination.getCoinSums(each_set_of_coins).toString());
}
}
}
Вывод:
[10, 20, 30]
[1, 2, 3, 4, 5, 6]
[10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
[10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140, 150, 160, 170, 180, 190, 200]
@ sendon1982 Рад помочь :)
ОП, ваш аккаунт взломали или что-то в этом роде? Похоже, вы были участником уже 5 лет, я думаю, вы знаете, как работает SO?