public class CollectionUtils
{
/**
* 合并2个 有序列表的交集
* @param c1
* @param c2
* @return List
*/
public static List<Integer> retainOrderListAll(List<Integer>c1,List<Integer>c2 )
{
if(c1.size()<=c2.size()){//长度小的列表作为参考列表
return retain(c1,c2);
}
else{
return retain(c2,c1);
}
}
/**
* 比较前提是2个列表都是 升序排序好的...
* @param minList
* @param maxList
* @return List
*/
private static List<Integer> retain(List<Integer> minList,List<Integer> maxList){
bre1:for( Iterator<Integer> it = minList.iterator();it.hasNext(); )
{
Integer int1 = it.next(); //当前参照值
bre2:for(Iterator<Integer> it2 = maxList.iterator();it2.hasNext();)
{
Integer int2 = it2.next(); //当前比较值;
////////===比较2个数值的大小 根据比较的结果进行3种操作=====//////
//// (1)如果 相等 那么就移除list2中当前值,进入list1下一轮循环
//// (2)如果 参照值int1 大于 比较值int2 那么删除小值int2 继续list2中的循环查找 -->(1)
//// (3)如果 参照值int1 小于 比较值int2 那么删除小值int1 继续list1中的循环-->(1);
//============值 匹配时==================== ;
if(int1.equals(int2)){
it2.remove();//list2中比较过的数值 直接删除...避免下次再次比较该数值;
continue bre1;//进入下一轮list1循环;
}
//=============未 匹配时=====================;
if(int1 > int2){
//参照值大于比较值时;
it2.remove();
continue;
}
//参照值小于 比较值时,说明此参照值肯定不会被匹配,直接删除 进入下一轮list1循环
if(int1 < int2){
it.remove();
continue bre1;
}
}
//=================list2为空时 list1中的所有剩余值全部移除 该判断要放在后面,以防列表被清空时,当前的it 没被移除直接进入下一次循环了;
if(maxList.size()==0){
it.remove();
continue;
}
}
return minList;
}
}
测试过
50000 条记录 和 33333条记录的两个列表 求交集时间是1800ms左右
100000条 和 66666条记录的两个列表 求交集时间是8000ms左右
因为it.remove 需要重新整理索引 所以速度耗费了很大一块
修正后:
public class CollectionUtils
{
/**
* 合并2个 求有序列表的交集
* 列表为null时候 那么就视为全集;
* @param c1
* @param c2
* @return List
*/
public static List<Integer> retainOrderListAll(List<Integer>c1,List<Integer>c2 )
{
//===========是否存在null列表对象==============
if(c1==null && c2==null){//都为null
return null;
}
else if(c1==null && c2!=null){//其中一个为null 返回另一个列表
return c2;
}
else if(c1!=null && c2 == null){
return c1;
}
//==========列表对象都不为null时======================
if(c1.size()<=c2.size()){//长度小的列表作为参考列表
return retain(c1,c2);
}
else{
return retain(c2,c1);
}
}
/**
* 比较前提是2个列表都是 升序排序好的...
* @param minList
* @param maxList
* @return List
*/
private static List<Integer> retain(List<Integer> minList,List<Integer> maxList){
// int compCount = 0;//比较次数;
List<Integer> r = new ArrayList<Integer>();
int index1 = 0;
int size1 = minList.size();
int index2 = 0;
int size2 = maxList.size();
loop1: for( ;index1 < size1;index1++){
loop2: for( ;index2 < size2;index2++ )
{
if(minList.get(index1).equals( maxList.get( index2))){
r.add( minList.get( index1));
index2++;
continue loop1;
}
if(minList.get(index1) > maxList.get( index2)){
continue;
}
if(minList.get(index1) < maxList.get( index2)){
continue loop1;
}
}
}
return r;
}
/**
* 判断列表 是否是一个空列表对象;
* 且非null;
* @param list
* @return boolean
*/
public static boolean isEmptyList(List list){
if(list!=null && list.size()==0){
return true;
}else{
return false;
}
}
}
测试后速度提高了几百倍
基本是线性复杂度 最高复杂度是 M+N
耗时在 几十ms
分享到:
相关推荐
在Java编程中,集合框架是...在实际应用中,`TreeSet`不仅适用于求并集,还可以用于求交集、差集等集合操作,是Java集合框架中的一个重要工具。了解和熟练掌握`TreeSet`的特性和操作方法对于提升Java编程能力至关重要。
如果list1和list2是String类型的List集合,我们也可以使用这个方法来获取它们的交集。 这篇文章分享了如何使用Java编程语言从两个List集合中提取相同的重复数据。这个方法可以用于任何类型的List集合,并且可以方便...
`equals()`方法会检查两个数组的引用是否指向同一个对象,以及两个数组的长度是否相同,如果这两个条件都满足,再逐个比较每个元素是否相等。但是,这并不适用于找出相同或不同的元素,它只能告诉我们两个数组是否...
给定两个列表`List1 = [0, 49, 1, 2, 3, 56, 5, 7, 8, 9, 10]` 和 `List2 = [1, 2, 4, 8, 9, 27, 0, 49, 56, 77]`,使用Lambda表达式编写一个Python程序来找出这两个列表的交集。 **解决方案**: ```python # 定义...
2. **丰富的数据类型**:Redis支持多种数据类型,包括但不限于二进制安全的字符串(Strings)、列表(Lists)、哈希(Hashes)、集合(Sets)以及有序集合(Ordered Sets)。 3. **原子操作**:所有的Redis操作都是原子性的...
### Redis设计与实现原理及运作机制 #### 一、内部数据结构 Redis 是一款高性能的键值存储系统,其高效性很大程度上得益于内部使用的多种...实现时,Redis会遍历第一个集合,并在第二个集合中查找不存在的元素。 ###...
String 是 Redis 最基础的数据类型,它是一个二进制安全的类型,可以存储任何数据,包括文本、图像或序列化的对象。每个键值对中的值最大可达 512MB。通过 `SET` 和 `GET` 命令,我们可以设置和获取键值对。例如: `...
- **代理**:一个对象可以代表另一个对象来实现接口。 **7.6 接口的赋值与转型** - **接口的赋值兼容**:检查两个接口是否可以相互赋值。 - **接口的转型**:将一个接口转换为另一个接口类型。 **7.7 使用接口...
比如`Collections.max(list)`获取列表中的最大值,`Collections.swap(list, i, j)`交换列表中两个位置的元素,以及`Collections.disjoint(set1, set2)`检查两个集合是否没有交集。 最后,对于源码部分,可能讲解了...
这种方式首先按第一个元素降序排序,相同的情况下再按照第二个元素升序排序,从而保证了排序的稳定性。 **2.4 Sorting by One Field, Then by Another(先按一个字段排序,再按另一个字段排序)** 对于需要多重...
在主函数中,创建了两个`IntegerSet`对象`s1`和`s2`,分别调用了它们的`srpx()`方法对输入的整数进行排序。接着,计算两个已排序数组的交集和并集。 6. **交集与并集**:交集是同时存在于两个数组中的元素,通过...
例如,数组是一组相同类型的数据的有序集合,可以在一个变量中存储多个值。列表则更加灵活,允许存储不同类型的数据,并支持动态增删元素。字典是键值对的集合,通过键来查找对应的值。集合则是一组不重复元素的无序...
在Java编程中,集合框架是处理对象集合的重要工具,提供了多种数据结构和操作方式。本实验主要关注两个方面:Java集合和XML编程。首先,我们深入理解Java集合框架中的Set接口及其具体实现。 1. **Set接口**:Set...
有序类型,如Integer和Cardinal,表示可以进行比较和排序的数值。它们具有最小和最大值,可以参与数学运算。 13. **布尔类型**: 布尔类型(Boolean)有两个可能的值:True和False,用于逻辑表达式和条件判断。 ...
- “求交”并非SQL标准中的一个操作,一般用来描述两个集合共有的元素。 ### 编程语言特性 3. **C++源程序中不能表示的数制**:C++支持多种数制表示。 - 选项 **A** 的二进制表示,在C++11及更高版本中是支持的,...
根据给定文件的信息,我们可以总结出一系列与计算机二级等级考试相关的知识点。以下是对各个问题的知识点解析: ### 1. VCD、DVD存储介质 **知识点:** - **磁性存储介质**:传统意义上,磁性存储介质通常指的是...
进阶的SQL特性如窗口函数允许我们在每个分组内进行有序计算,GROUPING运算符则用于处理分组层次。此外,还有其他特定DBMS支持的高级特性。 9. 通过应用程序 SQL可以与各种应用程序集成,如Web应用、桌面应用等,...
- **6.6.2 相交运算符**: 计算两个集合的交集。 - **6.6.3 并运算符**: 计算两个集合的并集。 - **6.6.4 差运算符**: 计算两个集合的差集。 - **6.6.5 子集运算符**: 检查一个集合是否是另一个集合的子集。 - **...