Сравнить элементы в массиве строк в Java

Question

Мне нужно написать метод, который будет сравнивать элементы в массиве строк и возвращать индекс наибольшего элемента. Это будет сделано рекурсивно с использованием подхода «разделяй и властвуй». У меня есть идея, и я просто искал, была ли моя идея правильной или ее нужно было сделать по-другому.

Я планировал посмотреть на массив с левой стороны на mid -1, затем посмотреть на mid, а затем на mid +1 справа. У меня есть переменная, которая будет отслеживать самый большой индекс, а затем сделать рекурсивный вызов для левой и правой сторон.

Это звучит как хороший способ решить эту проблему?

Это то, что я имею до сих пор:

---

public int longest()
{
    longest(0, a.length-1);
    return longestIndex;
}

private int longest( int left, int right)
{
    int longestIndex;
    int mid;

    if(left > right)
    {
        longestIndex = -1;
    }
    else if(left == right)
    {
        longestIndex = 0;
    }

    else
    {
        longestIndex = 0;

        mid = (left + right) / 2;
        longest(left, mid - 1);
        if (a[mid].compareTo(a[longestIndex]) > 0)
        {
            longestIndex = mid;
        }
        longest(mid + 1, right);            
    }            
    return longestIndex;
}

Кроме того, поскольку методы должны возвращать int, как бы я передал longestIndex n private-метод в public-метод, чтобы он отображался в моей тестовой программе при вызове longest?

Answer 1

Имеет ли значение для рекурсии? Использование рекурсии для этого звучит как случай:

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

---

Если бы я был вынужден использовать рекурсию, я бы сделал что-то вроде:

int longest(array):
    return longest_helper(0, 0, array)

int longest_helper(max_index, curr_idx, array):
    # base case: reached the end of array
    if curr_idx == array.length:
        return max_index

    if array[curr_idx].length > array[max_index].length:
        max_index = curr_idx

    # recursive call
    return longest_helper(max_index, curr_idx + 1, array)

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

---

Поскольку не похоже, что массив отсортирован, самый простой (и самый быстрый) способ сделать это - просто пройти через все это (псевдокод):

max_index  = 0
max_length = array[0].length

for index in 1 .. array.length:
    if array[index].length > max_length:
        max_length = array[index].length
        max_index  = index

return max_index

Answer 2

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

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

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