Разные слагаемые проблемы жадного алогрита

Question

Я пытаюсь решить проблему «Различные слагаемые» с помощью жадного алгоритма

Описание проблемы

Задача .Цель этой задачи состоит в том, чтобы представить данное положительное целое число ? в виде суммы максимально возможного числа попарно различных положительных чисел.То есть найти максимальное значение ?, такое, что ? можно записать в виде ?1 + ?2 + · · · + ??, где ?1, . . . , ?? - положительные целые числа и ?? ̸= ?? для всех 1 ≤ ? < ? ≤ ?.

Формат ввода. Ввод состоит из единственного целого числа ?.Ограничения.1 ≤ ? ≤ 10^9.

Формат вывода. В первой строке выведите максимальное число ?, чтобы ? можно было представить в виде суммы ? попарно различных натуральных чисел,Во второй строке выведите ? попарно различных натуральных чисел, которые суммируются до ? (если таких представлений много, выведите любое из них).

Мой код:

public class DifferentSummands {
    private static List<Integer> optimalSummands(int n) {
        List<Integer> summands = new ArrayList<Integer>();
        int start = 1;
        int newNumber = n;

        if (n == 2) {
            summands.add(2);
            return summands;
        }

        while (true) {
            if (summands.contains(newNumber - start)) {
                start++;
                continue;
            } else {
                newNumber -= start;
                summands.add(start);
                start++;
            }

            if (newNumber == 0) {
                return summands;
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        List<Integer> summands = optimalSummands(n);
        System.out.println(summands.size());

        for (Integer summand : summands) {
            System.out.print(summand + " ");
        }
    }
}

Мой код дает сбой, если ввод был настолько большим, что это занимает около 3,24 секунды, а максимальное доступное время составляет 1,5 секунды.

Answer 1

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

Мой код

private static HashSet<Integer> optimalSummands(int n) {
    HashSet<Integer> summands = new HashSet<>();
    int start = 1;
    int newNumber = n;
    if (n == 2) {
        summands.add(2);
        return summands;
    }

    while (true) {
        if (newNumber < 0) {
            Object[] value = summands.toArray();
            int secondlast = (int) value[summands.size() - 2];
            int last = (int) value[summands.size() - 1];

            summands.remove(last);
            summands.remove(secondlast);

            newNumber = secondlast + last -1;

        }
        if (summands.contains(newNumber - start) ) {
            start++;
            continue;
        } else {
            newNumber -= start;
            summands.add(start);
            start++;

        }

        if (newNumber == 0) {
            return summands;
        }
    }
}

Answer 2

Даже если мы можем решить это с помощью HashSet, но мы можем и без него.

Мы знаем, что summands имеют последовательные числа от 1 до start.Поэтому, вместо проверки списка, обратите внимание, что если newNumber-start <= start, то мы должны остановиться.Так что newNumber на данном этапе должен быть последним номером нашего ответа.

Пересмотр вашего кода в соответствии с минимизацией изменений,

...
        while (true) {
            if (newNumber-start <= start) { // possibly (newNumber <= start*2)
                summands.add(newNumber);
                newNumber = 0;
            } else {
...

Общая сложность времени теперь O(n^0.5).(Это был O(n) = O(n^0.5 * n^0.5) с List поиском)

Answer 3

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

У Гаусса есть формула для суммычисла от 1 до k .Это просто k (k + 1) / 2 .

Вам просто нужно найти самое большое k , такое что k (k + 1) / 2<= n </strong>.Из вышесказанного вы знаете, что если k больше, то вы не сможете разделить n на такое количество слагаемых, так что это самый большой ответ.

Также очень просто генерировать k слагаемых, которые добавляют к n - это просто сумма всех чисел от 1 до k-1 , а затем все, что осталось ( n - k (k-1) / 2 ).

Вы можете решить для k напрямую:

k (k + 1) / 2 <= n </strong>

k² + k - 2n <= 0 </strong>

k <= (sqrt (8n + 1) -1) / 2 </strong>

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

k = floor ((sqrt (8n + 1) -1) / 2)

Answer 4

При выполнении contains для ArrayList (переменная summands) он просматривает все значения в списке, чтобы найти, существует ли уже элемент.O (n) операция.

Попробуйте использовать HashSet вместо списка, для лучшей производительности O (1).

Если вы заботитесь о порядке элементов внутри вашего результата (слагаемых), выможет использовать LinkedHashSet.