java - 从数组中查找元素的最大长度

Question

我正在开发一个程序，我需要找出给定数组可以形成的最大链。

例子:

假设输入是:

Arr[0] = 5
Arr[1] = 4
Arr[2] = 0
Arr[3] = 3
Arr[4] = 1
Arr[5] = 6
Arr[6] = 2

现在如果我采用数组索引和相应的值，我可以形成的可能的最大链是

值为 5 的索引 0 --> 值为 6 的索引 5 --> 值为 2 的索引 6 --> 值为 0 的索引 2。这个循环重复所以这是我可以使用这个数组形成的最大链

这是我的代码:

public static int getMax(int[] nums) {
        int result = 0;
        for (int i = 0; i < nums.length; i++) {
            List<Integer> list = new ArrayList<>();
            list.add(i);
            int temp = i;
            while (true) {
                int next = nums[temp];
                if (list.contains(next)) {
                    break;
                } else {
                    list.add(next);
                    temp = next;
                }
            }
            result = Math.max(result, list.size());
        }
        return result;
    }

我已经提出了上述逻辑，但我发现在我的代码中我试图找到相同类型的多个链。

这意味着如果我打印我的列表它有这些值:

[0, 5, 6, 2]
[1, 4]
[2, 0, 5, 6]
[3]
[4, 1]
[5, 6, 2, 0]
[6, 2, 0, 5]

这里 0,5,6,2 链重复多次，有没有办法提高我的代码性能以避免像上面那样不必要的类似循环。

Answer 1

您可以通过检查该项目是否已包含在数组中来将您获得的每个值放入数组。然后当你迭代时，如果你在你填充的数组中得到一个数字，你可以使用 continue

忽略该迭代