Объединить дубликаты длинных в массив

Question

Я пытаюсь рекурсивно объединять / умножать повторяющиеся длинные значения в массиве. Так что, если у меня есть что-то подобное: long [] arr = {3, 5, 6, 6, 7} => long [] arr = {3, 5, 36, 7}

Вот что у меня есть:

    public static long[] merge(long[] ns, int i, Merger m) {
    m.merge();
    if(i > ns.length) return new long[0];
    if(i < 0) return merge(ns, 0, m);
    else {
        if(ns[i] != ns[i+1]) {
            return append(merge(ns, i-1, m), ns[i+1]);
        }
        else {
            return append(merge(ns, i-1, m), ns[i] * ns[i+1]);
        }
    }

    public long[] append(long[] old, long newLast) {
        long[] result = Arrays.copyOf(old, old.length + 1);
        result[old.length] = newLast;
        return result;
    }
}

Но он застрял в своей рекурсии.

Answer 1

Есть несколько случаев, которые не ясны из подхода, который вы выбрали.

Что происходит, когда несколько экземпляров одного и того же значения?Они просто умножаются?В своей текущей логике вы проверяете, есть ли ns[i] != ns[i+1], что предполагает, что a.список, если отсортирован, .b.что вхождения встречаются только парами.

Чтобы понять, почему (a) выполняется, ваш текущий подход не умножит два 6 s, если ваш входной список [3,6,5,6,7],Это допустимое предположение?

Чтобы понять, почему (b) выполняется, предположим, что вы использовали для ввода [1,3,5,6,6,6,7].В этом случае при умножении первых двух вхождений на 6 ваш результирующий список будет [1,3,5,36,6,7], и ваша текущая логика не умножится на 36 и 6.

Это предназначено?

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

Предполагая, что эти два предположения верны для конкретной проблемы, которую вы пытаетесь решить, приведенная ниже реализация работает.(Примечание: это реализовано в Python. Если вы ищете решение, специфичное для Java, вам следует изменить свой вопрос, указав его + добавить тег Java к вашему сообщению. Кто-то, свободно владеющий Java, может вам помочь. Это решениепытается максимально приблизиться к вашему подходу.)

def merge(ns, i, resultant_list = None):
    if resultant_list is None:
        resultant_list = []

    if i > len(ns)-1:
        return resultant_list

    else:
        if i == len(ns)-1:
            append(resultant_list, ns[i])
            return resultant_list

        elif(ns[i] != ns[i+1]):
            append(resultant_list, ns[i])
            return merge(ns, i+1, resultant_list)

        else:
            append(resultant_list, ns[i] * ns[i+1])
            return merge(ns, i+2, resultant_list)        

def append(old, newLast):
    old.append(newLast)
    return old