如何对两个整数数组进行顺序不敏感比较

Question

我想要能够以这种方式比较的Java代码(例如):

<1 2 3 4>  = <3 1 2 4>
<1 2 3 4> != <3 4 1 1>

我不能使用hashmap表或任何东西; 只是没有库的纯代码.

我知道有两种方法.

1. 对它们进行排序并按索引比较数组索引

2. 使用两个for循环并将外部索引与内部索引进行比较.我一直在尝试这个但仍然没有工作:

   for(int i = 0; i < n; i++)
   {
       for(int j = 0; j < n; j++)
       {   
           if(a[i] != a[j] && j == n)
               return false;
       }
   }
   return true;
   

代码有什么问题吗？谢谢

Answer 1

排序和比较.你不能比这更好地获得复杂性,你对速度所做的任何"改进"都会冒你的代码出错的风险.

[编辑]实际上......如果你知道你的数字相对较小(例如:数组只包含0到1000之间的数字),那么O(n)就有了另一种选择.这样的事情(抱歉,如果语法错误,我最近没有使用java):

int count[1001]; // already intialized to 0

for(int i=0;i<n;i++){ count[a[i]]++; count[b[i]]--;}
bool arrays_identical = true;
for(int i=0;i<=1000 && arrays_identical; i++)
    arrays_identical &= count[i]==0;

免责声明:此代码不包含"健全性检查"(即数组实际上长度为"n",数字在规定的时间间隔内) - 它只是为了说明原理.