algorithm - 如何判断两个序列是否因排列不同？

Question

给定任意两个由 n 个实数组成的序列，比如 (a1,a2,...,an) 和 (b1,b2,...,bn)，如何判断一个序列(也可以看作一个向量)是另一个的排列？

我计划开发一种算法并在 Matlab 上运行它来完成这项工作。我只能想到一个算法，花费n!次:尝试 n 中的所有排列。

有没有更快的算法？

Answer 1

首先，为什么n! ？如果对于每个 ai，你在 bi 中搜索一个匹配项，你将得到 O(n^2)。无论如何，使用复杂度为 O(nlogn) 的排序更有效。

A=[3,1,2,7];
B=[2,3,1,7];
isPermutated=isequal(sort(A),sort(B))