java - 用Java查找两个数组是否彼此递归排列

我需要构建一个递归函数，如果数组true是数组a的排列，则返回b，否则返回。

public static boolean isPermutation (int [] a, int [] b)

可以向函数添加参数。
不能使用本地数组。
不能使用循环。
无法使用库函数。
无法更改数组。


有人有主意吗？

最佳答案

这应该为您工作，这基本上是使用递归实现的循环。这应该在二次时间内执行。

public static boolean isPermutation(int[] a, int[] b, boolean[] ataken, boolean[] btaken, int iter, int totalTaken, int aidx, int bidx)
{
    if (a.length != b.length) return false;

    // totalTaken is a count of the number of matches we've "taken"
    if(totalTaken == a.length) return true;

    // don't "loop" b
    if(bidx >= b.length)
    {
        return false;
    }

    // we should loop through a... this will yield a quadratic runtime speed
    if(aidx >= a.length)
    {
        if (iter < a.length)
        {
            return isPermutation(a, b, ataken, btaken, iter + 1, totalTaken, 0, bidx);
        }

        // finished our loop, and "totalTaken" wasn't the whole array
        return false;
    }

    // found a match for this b[bidx]
    if(a[aidx] == b[bidx] && !ataken[aidx] && !btaken[bidx])
    {
        ataken[aidx] = true;
        btaken[bidx] = true;
        return isPermutation(a, b, ataken, btaken, iter, totalTaken + 1, aidx + 1, bidx + 1);
    }

    // loop through a
    return isPermutation(a, b, ataken, btaken, iter, totalTaken, aidx + 1, bidx);
}

您可以使用填充有ataken的btaken和false数组来调用它，但是它们的长度分别与a和b相同。

var isPerm = staticClassName.isPermutation(a, b, ataken, btaken, 0, 0, 0, 0);