最近做的一个项目,需要校验两个List是否相等的问题,我们看看如何比较两个数组相等。数组是一个连续的内存空间,所以一般来说,两个数组相等,就是意味着他们有相同的长度,相同的元素,以及相同的顺序。我们看看JDK的Arrays.equals()实现就一目了然了。
public static boolean equals(int[] a, int[] a2) { if (a==a2) return true; if (a==null || a2==null) return false; int length = a.length; if (a2.length != length) return false; for (int i=0; i<length; i++) if (a[i] != a2[i]) return false; return true; }
大致分成下面4个步骤:
a.检查是否指向同一个地址(不同引用);
b.非空检查;
c.长度检查;
d.顺序和对应的元素相等检查。(依次比较,只要一个不等就返回false)
而对于List来说,没有固定的顺序(ArrayList底层是数组,可以用数组的比较方法;但是其他的List,如LinkedList,就不一样了。),或者说顺序对List来说不是一个重要的属性。所以可以考虑其他方式来检查两个List是不是包含相同的元素。
如JDK的Collection.containsAll(),只是是对每个元素进行contains()操作。但是List允许重复的元素,所以这里无法比较重复元素的数量:
public boolean containsAll(Collection<?> c) { for (Object e : c) if (!contains(e)) return false; return true; }
那么,如何对无序的元素进行equal比较呢?
比较简便直观的方法,就是分别对两个list排序,然后一个一个比较,只要不相等,则返回false,如果全部都相等,则返回true。
if (a.size() !=b.size()) return false; Collections.sort(a); Collections.sort(b); for (int i = 0; i <a.size(); i++) { if(!a.get(i).equals(b.get(i))) return false; } return true;
但是这样两次排序,效率还是比较低的。所以可以通过Map来实现:
先存入HashMap,key为元素,value为出现的次数,然后再逐个元素比较出现的次数,这样能确保元素都包含,而且出现次数相同。
如下代码所示,具体可以参考org.apache.commons.collections.CollectionUtils.isEqualCollection() 。(CollectionUtils中大量使用了getCardinalityMap()的特性)
private static final Integer INTEGER_ONE = 1; public static boolean isEqualCollection(Collection a, Collection b){ if (a.size() !=b.size()) { // size是最简单的相等条件 return false; } Map mapa = getCardinalityMap(a); Map mapb = getCardinalityMap(b); // 转换map后,能去掉重复的,这时候size就是非重复项,也是先决条件 if (mapa.size() !=mapb.size()) { return false; } Iterator it =mapa.keySet().iterator(); while (it.hasNext()) { Object obj = it.next(); // 查询同一个obj,首先两边都要有,而且还要校验重复个数,就是map.value if (getFreq(obj,mapa) != getFreq(obj, mapb)) { return false; } } return true; } /** * 以obj为key,可以防止重复,如果重复就value++ * 这样实际上记录了元素以及出现的次数 */ public static Map getCardinalityMap(Collection coll) { Map count = new HashMap(); for (Iterator it =coll.iterator(); it.hasNext();) { Object obj =it.next(); Integer c =(Integer) count.get(obj); if (c == null) count.put(obj, INTEGER_ONE); else { count.put(obj, newInteger(c.intValue() + 1)); } } return count; } private static final int getFreq(Objectobj, Map freqMap) { Integer count =(Integer) freqMap.get(obj); if (count != null) { return count.intValue(); } return 0; }
相关推荐
比较两个集合是否相同(比较两个List内容是否相同) 利用Java反射机制,获取到字段名、方法名、字段值,进行逐个比较,此处本人封装好了工具类,接收的是泛型,调用者只需要传入两个实体List即可进行比较,返回true...
java计算同一个list中是否有相同的值
今天小编就为大家分享一篇关于Java判断2个List集合是否相等(不考虑元素的顺序)的文章,小编觉得内容挺不错的,现在分享给大家,具有很好的参考价值,需要的朋友一起跟随小编来看看吧
Contains 方法 确定某元素是否在HashSet中 Exists 方法 确定HashSet是否包含于指定条件相匹配的元素 ExceptWith 方法 从当前HashSet移除指定集合中的所有元素 IntersectWith 方法 修改当前的HashSet对象,以...
今天小编就为大家分享一篇vue实现将一个数组内的相同数据进行合并,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
思路:将链表中的元素都保存list中,并判断这个list和反转后的list,是否相同,如果相同,则回文;否则,则不回文。 性能分析:时间复杂度为O(n);空间复杂度为O(n) [因为用到了extra space list] 方法2 思路:...
安卓开发--Android连连看游戏源码.zip ... Bitmap对象和图片资源的ID,Bitmap对象用于在游戏界面上绘制方块,而图片资源ID代表了Piece对象的标识,当两个Piece封装的图片资源的ID相等时,即可认为Piece上的图片相同。
28、设计4个线程,其中两个线程每次对j增加1,另外两个线程对j每次减少1。写出程序。 以下程序使用内部类实现线程,对j增减的时候没有考虑顺序问题。 public class ThreadTest1{ private int j; public static ...
如果对两个引用调用hashCode()会得到相同的结果。(默认情况下,Object的hashCode()返回对象的32位jvm内存地址。)因此,如果对象所属的类没有覆盖Object的hashCode(),指向同一对象的引用调用hashCode的值相等,而...
44.两个对象值相同(x.equals(y) == true),但却可有不同的hash code,这句话对不对? 答:不对,有相同的hash code。 45.swtich是否能作用在byte上,是否能作用在long上,是否能作用在String上? 答:switch(expr1...
=或者==:判断两个值是否相等. 2. !=:判断两个值是否不等. 3. >或者gt:判断左边值是否大于右边值 4. >=或者gte:判断左边值是否大于等于右边值 5. <或者lt:判断左边值是否小于右边值 6. 或者lte:判断左边值是否...
6.数据结构中评价算法的两个重要指标是(时间复杂度和空间复杂度) 【北京理工大学 2001 七、1(2分)】 7. 数据结构是研讨数据的_(1)物理结构_和_(2)逻辑结构 _,以及它们之间的相互关系,并对与这种结构定义...
数据结构,如何遍历List中的元素? 如果要按照键值保存或者访问数据,使用什么数据结构? 要掌握Collection相关的接口和类的使用 56.使用StringBuffer类与String类进行字符串连接时有何区别? 57.调用Thread类的...
抽象包括两个方面,一是过程抽象,二是数据抽象。 2.继承: 继承是一种联结类的层次模型,并且允许和鼓励类的重用,它提供了一种明确表述共性的方法。对象的一个新类可以从现有的类中派生,这个过程称为类继承...
// 一个包含两个元素的数组 $a[0] = "first"; $a[1] = "second"; $a[] = "third"; // 添加数组元素的简单方法 // 现在$a[2]被赋值为"third" echo count($a); // 打印出3,因为该是...
#eq#是逻辑运算符,用来判断是否“相等”,可参考§4. &1可看作派生集的第1个原始父集的索引,它取遍该原始父集的所有成员;&2可看作派生集的第2 个原始父集的索引,它取遍该原始父集的所有成员;&3,&4,……,...
(但是请注意:两个不同但结构上等效的委托类型的实例可能会比较为相等),准确地说,两个具有相同参数列表、签名和返回类型的不同的委托类型被认为是不同的委托类型。委托实例所封装的方法集合称为调用列表。 5, ...
(提示: 插入法排序的思路是:先对数组的头两个元素进行排序, 然后根据前两个元素的情况插入第三个元素,再插入第四个元素…)。 (15)爱因斯坦数学题。爱因斯坦曾出过这样一道数学题:有一条长阶梯,若每步跨2...
在for语句中,用gets函数分别输入各个元素中两个成员的值。然后又在for语句中用printf语句输出各元素中两个成员值。 结构指针变量 结构指针变量的说明和使用一个指针变量当用来指向一个结构变量时, 称之为结构...