Поиск в графе java

166

01 августа 2019, 06:50

Дан массив A длины (n+1), содержащий натуральные числа от 1 до n. Найти любой повторяющийся элемент за время O(n), не изменяя массив и не используя дополнительной памяти.

public static void main (String[] args){
    int[] array = {7, 5, 2, 5, 3, 2, 1, 8, 4};
    newFind(array);
}
public static void newFind(int[] mas){
    int index = mas.length;
    int el = mas[index - 1];
    int object = mas[el - 1];
    while (true){
        object = mas[el - 1];
        el = mas[object - 1];
        el = mas[el - 1];
        el = mas[el - 1];
        if (object == el) {
            System.out.println(el);
            break;
        }
    }
}

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

Answer 1

Еще одна попытка помочь... :)
Простите, что не на Java, но, думаю, что вы сможете перевести. На C++ нужное вам решение имеет примерно следующий вид (понятно, что это не единственный способ... но мне было проще написать решение с нуля):

int Double(int * A, int N /*длина массива*/)
{
    int p = N, q = N;
    for(int i = 0; i < N; ++i) p = A[p-1];
    int k = 1, s = p;
    while((p=A[p-1]) != s) ++k;
    p = N;
    for(int i = 0; i < k; ++i) p = A[p-1];
    for(;p != q;)
    {
        p = A[p-1];
        q = A[q-1];
    }
    return p;
}

Думаю, что на Java это будет выглядеть как

public static void newFind(int[] A)
{
    int N = mas.length;
    int p = N, q = N;
    for(int i = 0; i < N; ++i) p = A[p-1];
    int k = 1, s = p;
    while((p=A[p-1]) != s) ++k;
    p = N;
    for(int i = 0; i < k; ++i) p = A[p-1];
    for(;p != q;)
    {
        p = A[p-1];
        q = A[q-1];
    }
    System.out.println(p);
}

Работает за O(N), лишней памяти не просит...