主页 / 问题 / 930481
Accepted
Александр
Asked:2020-01-10 19:31:22 +0000 UTC2020-01-10 19:31:22 +0000 UTC

在java图中搜索

  • 772

给定一个长度为 (n+1) 的数组 A，其中包含从 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;
        }
    }
}

我是这样实现的，但是如果循环有更多或更少的步骤，那么程序就会中断。我的问题是我不明白如何计算循环长度到重复元素并在屏幕上显示元素。请帮帮我。

java

1 个回答

  1. Best Answer

    另一个尝试帮助... :)
    对不起，不是在 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) 中运行，不要求额外的内存......

    • 2

相关问题