java - 使用数组数组 (int[][]) 创建一个方法来查找给定排列中的所有循环

Question

关闭。这个问题需要多问 focused 。目前不接受答案。

---

想要改进此问题吗？更新问题，使其仅关注一个问题 editing this post .

已关闭 9 年前。

Improve this question

所以我只能使用标准数组来实现此目的，仅此而已。我必须找到一种方法来创建一种方法，该方法可以找到给定排列中的所有循环并将它们作为数组的数组对象返回。然后我必须将每个数组的最低值作为数组的第一个条目。然后按最低顺序对它们进行排序。

我不能使用数组列表或集合或任何东西。

编辑:我所说的循环是指获取初始对象的整数值并找到它对应的索引值。取该索引处的整数值并执行相同的操作。继续执行此操作，直到它指向已引用的对象。

示例:[0, 4, 2, 8, 7, 9, 1, 6, 5, 3]

将是这些周期:[0] [4, 8, 5, 7, 6, 9, 3, 2] [1]

并返回:[0], [1], [2, 4, 8, 5, 7, 6, 9, 3]

或

该数组:[2, 4, 8, 1, 5, 3, 9, 0, 7, 6]

将是这些周期:[2, 8, 7, 0] [4, 5, 3, 1] [9, 6]

并返回:[0, 2, 8, 7], [1, 4, 5, 3], [6, 9]

我很迷茫，任何帮助都会很棒。提前致谢!

Answer 1

不要问我为什么花时间这样做。

编辑:现在完全可以工作

public class Main {

    public Main()
    {

    }

    public static void main(String[] args)
    {
        int array[] = {0, 4, 2, 8, 7, 9, 1, 6, 5, 3};
        Main m = new Main();
        int[][] cycles = m.getCycles(array);
        for (int i = 0; i < cycles.length; i++)
        {
            System.out.print("[");
            for (int j = 0; j < cycles[i].length; j++)
            {
                System.out.print(cycles[i][j]);
                if (j < cycles[i].length - 1)
                    System.out.print(", ");
            }
            System.out.println("]");
        }
        System.out.println("end debug");
    }

    public int[][] getCycles(int[] array)
    {
        int[][] cycles = new int[array.length][array.length];

        // initialize the cycles to all -1s, cuz they'll never be in the array
        for (int i = 0; i < cycles.length; i++)
        {
            for (int j = 0; j < cycles[i].length; j++)
            {
                cycles[i][j] = -1;
            }
        }

        int i = 0;

        do {
            int nextElement = array[i];

            int j = 0;
            do {
                cycles[i][j] = nextElement;
                nextElement = array[nextElement];
                j++;
            } while (!elementInArray(cycles[i], nextElement) && j < array.length);


            i++;
        }  while (!arrayHasCycled(array, cycles) && i < array.length);


        cycles = removeNegativeOnes(cycles, i);

        for (i = 0; i < cycles.length; i++)
        {
            pushForward(cycles[i]);
        }

        return cycles;
    }

    public boolean elementInArray(int[] array, int element)
    {
        for (int i = 0; i < array.length; i++)
        {
            if( array[i] == element)
                return true;
        }

        return false;
    }

    public int[][] removeNegativeOnes(int[][] cycles, int numCycles)
    {
        int [][] newCycles = new int[numCycles][];
        for (int i = 0; i < numCycles; i++)
        {
            int realLenOfCycle = indexOf(-1, cycles[i]);
            newCycles[i] =  new int[realLenOfCycle];
            for (int j = 0; j < newCycles[i].length; j++)
            {
                newCycles[i][j] = cycles[i][j];
            }
        }

        return  newCycles;
    }

    public int indexOf(int element, int[] array)
    {
        int index =  -1;

        for (int i = 0; i < array.length; i++)
        {
            if (array[i] == element)
                return i;
        }

        return index;
    }

    public boolean arrayHasCycled(int[] array, int[][] cycles)
    {
        for (int i = 0; i < array.length; i++)
        {
            boolean cycleHasValue = false;
            for (int j = 0; j < cycles.length; j++)
            {
                for (int k = 0; k < cycles[j].length; k++)
                {
                    if (cycles[j][k] == array[i])
                        cycleHasValue = true;
                }
            }
            if (!cycleHasValue)
                return false;
        }

        return true;
    }

    public void pushForward(int [] array)
    {
        int lastElement = array[array.length - 1];
        for (int i = array.length - 1; i > 0; i--)
        {
            array[i] = array[i - 1];
        }

        array[0] = lastElement;
    }
}

输出:

[0]
[1, 4, 7, 6]
[2]
[3, 8, 5, 9]

据我了解，您需要创建一个执行以下算法的代码:

1. 创建一个一维整数数组，array
2. 对于该数组中的每个元素，nextElement 执行以下操作:
3. 创建一个新的一维数组 currCycle，该数组将添加到二维数组 cycles 中。
4. 将该数组的第一个元素设置为 nextElement。
5. nextElement 然后变为 array[nextElement]
6. 如果 nextElement 已在 currCycle 中，则继续处理 array 的下一个元素
7. 检查array的所有元素是否都在cycles内，如果是，则停止执行该算法。
8. 最后，将循环作为二维数组返回，其中包含正在使用的索引，而不是该索引处的元素，这就是当前数组的组成部分。要实现这一点，只需循环地(在正常意义上)将数组的每个元素向前推一个索引即可。

这并不完全遵循您的示例，但我认为您的示例可能格式错误，例如:

An example: [0, 4, 2, 8, 7, 9, 1, 6, 5, 3]

would be these cycles : [0] [4, 8, 5, 7, 6, 9, 3, 2] [1]

and return this: [0], [1], [2, 4, 8, 5, 7, 6, 9, 3]

第一个元素0是0，所以当你得到0时，它已经在当前循环中，所以转到下一个元素，即索引1处的元素，即4。一旦到达4，就转到第四个元素元素，是 7 而不是 8!

 0  1  2  3  4
[0, 4, 2, 8, 7...