如何对两个整数数组进行顺序不敏感比较 [英] How to compare two arrays of integers order-insensitively
问题描述
我想要以这种方式比较的Java代码(例如):
I want Java code that can compare in this way (for example):
<1 2 3 4> = <3 1 2 4>
<1 2 3 4> != <3 4 1 1>
我不能使用hashmap表或任何东西;只是没有库的纯代码。
I can't use hashmap table or anything; just pure code without library.
我知道有两种方法。
- 对它们进行排序并比较数组index by index
-
使用两个for循环并将外部索引与内部索引进行比较。我一直在尝试这个但仍然没有工作:
- sort them and compare the array index by index
use two for loops and compare the outer index with the inner index. I have been trying with this but still not working:
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;
代码有什么问题?谢谢
推荐答案
排序&相比。你不能比这更好地获得复杂性,你对速度所做的任何改进都会冒你的代码出错的风险。
Sort & compare. You can't get the complexity better than that, and any "improvement" that you do on the speed comes at the risk that your code will be wrong.
实际上....如果你知道你的数字相对较小(例如:数组只包含0到1000之间的数字),那么在O(n)中就有另一种选择。这样的事情(抱歉,如果语法错误,我最近没有使用java):
[edit] Actually.... if you know your numbers are relatively small (e.g. say: the arrays only contain numbers between 0 and 1000), that there's an alternative in O(n). Something like this (sorry if the syntax is wrong, I didn't use java lately):
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,数字在规定的时间间隔内) - 它只是为了说明原理。
Disclaimer: this code doesn't contain "sanity checks" (i.e. the arrays are really of length "n", the numbers are in the prescribed interval) - it's only to illustrate the principle.
这篇关于如何对两个整数数组进行顺序不敏感比较的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!