`

两集合求交集的算法比较

阅读更多
常常看javaeye的问答频道,想从已有答案的问题中找一些灵感。去看看别人是怎么思考的。

  今天看到的问题是:  http://www.iteye.com/problems/21324


   就是对两集合求交集

   看到一个比较优的解答是

Arrays.sort(array_1);  
Arrays.sort(array_2);  
int len = array_1.length  
for (int i = 0; i < len; i++)  
{  
 if (Arrays.binarySearch(array_2, array_1[i]) != -1)  
      print array_1[i];  
 }  


排序后,这个算法的复杂度是: M*log2N

数据结构中有个已排序的两集合求并集的例子。稍微改造:

var a=[1,3,5,3,2,4,8];
var b=[6,5,3,7,9,2];
Array.sort(a);
Array.sort(b);
for(var indexA=0,lenA=a.length, indexB=0,lenB=b.length; indexA<lenA && indexB<lenB;  ) {
        if(a[indexA] == b[indexB]) {
              document.writeln(a[indexA] + "<br>");
               indexA++;
                indexB++;
          }
        else if (a[indexA] < b[indexB]) {
            indexA++;
        }
        else {
            indexB++;
        }    
}

这个算法的排序后的复杂度M+N.

呵呵,不是一个数量级的算法比较。
附上:  常用的javascript集合操作:  http://4umi.com/web/javascript/array.php
0
0
分享到:
评论

相关推荐

    求两集合的交集 求两个集合的交集

    总结起来,C++ 中求两个集合交集的方法主要包括使用`std::set_intersection`函数以及手动迭代比较。前者在效率和简洁性上更具优势,后者则更为灵活,适应性更强。在实际应用中,应根据具体需求选择合适的方法。在...

    N个集合求交集C语言代码

    4. **多集合交集算法的设计与实现** #### 链表的基本操作 本程序主要通过链表来表示集合。链表是一种常用的数据结构,每个元素由数据部分和指向下一个元素的指针组成。 - **定义链表节点**:`typedef struct ...

    用顺序表完成2个集合的交集与并集以及各个集合的情况

    1.有序顺序表的元素按照从小到大有序存储; 2.实现有序顺序表的类模板,它的操作如下: ...3.用有序顺序表表示集合,实现两个有序顺序表的并和交(并和交仍是有序顺序表)并分析它们的时间复杂度;

    MATLAB求交集和并集代码

    根据给定的部分内容,我们可以逐步解析并完善代码,以实现求两个集合的交集和并集的功能。 ##### 3.1 定义符号变量 ```matlab syms abcdefghij ``` 这里使用`syms`定义了十个符号变量`a`至`j`,通常用于数学表达式...

    算法设计求交集

    设 A={a1,a2,…,an}, B={b1,b2,…,bn}是整数集合,其中 m=O(log n)。要求设计一个算法求集 合 C=A∩B。提示:使用二分查找技术。

    两个矩形求交快速算法

    在计算机科学领域,特别是在图形学、游戏开发以及空间数据处理中,两个矩形求交集的快速算法是一项基础且关键的技术。本文旨在深入探讨这一算法的原理与实现,特别是针对不同矩形相对位置下的交集计算策略。 ### ...

    求两个有序单链表的交集

    集合的交集、并集、差集运算是考察的常规内容,这里给出交集的代码,并集跟差集的类似

    取两个集合的交集

    计算两个集合的交集可以采用多种方法,下面介绍几种常见的算法: - **双循环法**:这种方法是最直观的,但效率较低。它的基本思路是遍历第一个集合中的每个元素,并检查该元素是否也存在于第二个集合中。如果存在,...

    集合运算 求并集和交集

    集合运算通常包括求并集、交集和差集等操作,这些在编程中非常常见,特别是在处理数据时。本篇文章将深入探讨如何用线性表,特别是顺序表来实现集合的求并集和交集运算。 首先,我们需要理解什么是顺序表。顺序表是...

    求交集和非交集

    在编程和数据处理中,"求交集和非交集"是一个常见的操作,尤其是在数据分析、算法设计和数据库查询中。交集是指两个或多个集合共有的元素,而非交集则是指存在于至少一个集合中但不在所有集合中的元素。在本篇内容中...

    集合幂级数的性质与应用及其快速算法

    例如,两个集合的并集对应于级数中的加法,而两个集合的交集则可以类比于乘法。这些集合运算的性质,如交换律、结合律、分配律等,为集合幂级数的性质提供了基础。 在研究集合幂级数的性质时,文章提到了三种常见的...

    2_链表_求la和lb的交集_

    总之,解决这个问题的关键在于利用已排序的特点以及集合的高效查找特性,通过迭代遍历两个链表来找到它们的交集。这既考验了对链表数据结构的理解,也展示了如何巧妙地应用辅助数据结构来优化算法效率。在实际编程时...

    求两个数组的交集

    总结来说,求两个数组的交集可以通过哈希表或集合数据结构实现,两者都能在O(n)的时间复杂度内完成任务。选择哪种方法取决于具体需求,如是否考虑元素顺序、对空间复杂度的要求以及所用编程语言的支持。

    两个多边形的并交差

    在计算机图形学中,多边形的并集、交集和差集操作是常见的几何算法,主要用于图形处理、碰撞检测、图像分析等领域。本话题主要探讨如何计算两个简单多边形(可以是凸多边形或凹多边形)的并集、交集和差集。 首先,...

    两个有序数组求交集,C++

    所谓“交集”,是指两个集合共有的元素组成的集合。当两个数组均为有序数组时,求解交集的操作可以变得更加高效。 #### 2. 代码解析 下面是对给定代码的详细分析: ```cpp #include using namespace std; int ...

    C++实现字符串求交集、并集、差集

    要实现两个集合的交集,可以遍历第一个集合的每个元素,在第二个集合中查找是否存在。如果存在,则将该元素添加到结果集合中。 #### 并集(Union) 上述代码中的`Append`函数实际上已经实现了简单的并集操作。...

    java 二个数组的交集,算法

    在Java编程中,处理两个数组的交集是常见的数据处理任务,这通常涉及到集合操作或者算法的应用。交集是指两个数组中都存在的元素组成的集合。本文将深入探讨如何使用不同的方法来找出两个数组的交集,并提供相关的...

    jihe.rar_visual c_集合的交集

    在编程领域,集合的交集、并集和差集是数据结构与算法中的基础概念,尤其是在处理一组元素的关系时非常常见。在这个名为"jihe.rar"的压缩包中,我们推测包含了一个用Visual C++实现的程序,该程序用于演示如何进行...

    ACM算法集集合

    参加acm大赛的同学很好的资源。连包含各种算法思想。

Global site tag (gtag.js) - Google Analytics