`
pcajax
  • 浏览: 2157175 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

判断两个数组中是否存在相同的数字

阅读更多

判断两个数组中是否存在相同的数字

给定两个排好序的数组,怎样高效得判断这两个数组中存在相同的数字?
这个问题首先想到的是一个O(nlogn)的算法。就是任意挑选一个数组,遍历这个数组的所有元素,遍历过程中,在另一个数组中对第一个数组中的每个元素进行binary search。用C++实现代码如下:

bool findcommon(int a[],int size1,int b[],int size2)
{
     int i;
     for(i=0;i<size1;i++)
     {
          int start=0,end=size2-1,mid;
          while(start<=end)
          {
               mid=(start+end)/2;
               if(a[i]==b[mid])
                    return true;
               else if (a[i]<b[mid])
                    end=mid-1;
               else
                    start=mid+1;
          }
     }
     return false;
}

后来发现有一个 O(n)算法。因为两个数组都是排好序的。所以只要一次遍历就行了。首先设两个下标,分别初始化为两个数组的起始地址,依次向前推进 。推进的规则是比较两个 数组中的数字,小的那个数组的下标向前推进一步,直到任何一个数组的下标到达数组末尾时,如果这时还没碰到相同的数字,说明数组中没有相同的数字。

bool findcommon2(int a[], int size1, int b[], int size2)
{
     int i=0,j=0;
     while(i<size1 && j<size2)
     {
          if(a[i]==b[j])
               return true;
          if(a[i]>b[j])
               j++;
          if(a[i]<b[j])
               i++;
     }
     return false;
}
分享到:
评论

相关推荐

    js判断数组是否相等的方法

    在JavaScript中,判断两个数组是否相等是一个常见的需求,尤其在处理数据比较或者验证时。根据标题和描述,我们可以区分两种不同的场景: 1. **数组完全相等**:在这种情况下,不仅要求数组中的元素相同,而且元素...

    C# 如何判断一个Byte数组中是否存在某些连续的数据).txt

    - 首先计算两个数组的长度。 - 使用外层循环遍历大数组中的每个可能的起始位置。 - 内层循环用于比较从当前起始位置开始的子数组与模式数组是否完全相同。 - 如果在某个位置找到匹配,则返回该位置的索引。 - ...

    易语言快速判断数组中的数值

    在这个"易语言快速判断数组中的数值"的主题中,我们主要探讨如何在易语言中高效地检查一个数值是否存在于一个数值数组之中。 在易语言中,数组是一种数据结构,可以存储同一类型的数据集合。数组由一个或多个元素...

    IOS开发之判断两个数组中数据是否相同实例详解

    总结来说,这个实例展示了如何在Objective-C中通过排序和比较元素来判断两个数组是否具有相同的数据。这种方法的关键在于排序以消除顺序影响,然后逐个比较元素。在实际的iOS开发中,这种技巧可用于验证数据一致性,...

    JavaScript比较两个数组的内容是否相同(推荐)

    在JavaScript中,比较两个数组的内容是否相同并非像比较基本类型那样简单,因为数组是对象,而`==`和`===`操作符在比较对象时,只会检查它们是否指向同一个内存地址,即比较的是引用,而不是内容。因此,直接使用`==...

    java 判断一个数组中的数值是否连续相邻的方法

    在 Java 编程语言中,判断一个数组中的数值是否连续相邻是一个常见的问题。今天,我们将分享一种简洁的方法来解决这个问题。 方法原理 该方法的主要思想是,遍历数组,并记录数组中的最小值和最大值。如果数组中的...

    详解JS取出两个数组中的不同或相同元素

    在JavaScript中,处理数组是常见的任务之一,特别是比较和操作两个数组以找出它们之间的差异或相同元素。在本文中,我们将深入探讨如何使用JS来实现这个功能。 首先,我们要了解几种核心的数组方法,这些方法在处理...

    JS判断数组里是否有重复元素的方法小结

    然后遍历排序后的数组,比较相邻的两个元素是否相同,如果相同,则说明原数组中存在重复的元素。这种方法适用于数字和字符串的比较,并且可以准确判断出重复元素。 4. 使用哈希表(对象)来判断重复 第四种方法是...

    Java查找不重复无序数组中是否存在两个数字的和为某个值

    Java查找不重复无序数组中是否存在两个数字的和为某个值 本文主要讲述了如何在Java中查找不重复无序数组中是否存在两个数字的和为某个值的问题。该问题可以使用哈希表来解决,时间复杂度为O(N)。 首先,需要将数组...

    javascript检测两个数组是否相似

    然而,JavaScript中的数组并没有内置的方法来直接判断两个数组是否“相似”。相似在这里指的是两个数组的元素相同,但顺序可以不同。由于JavaScript中数组的比较是基于引用的,所以不能使用等号运算符`==`或全等...

    js使用for循环查询数组中是否存在某个值

    在上述代码中,我们创建了一个数组,并通过`alert`函数来显示数组中是否存在数字8。如果存在,将会弹出提示框显示`true`;如果不存在,则不会有任何显示。 总结来说,使用for循环来查询数组中是否存在某个值,是...

    php下判断数组中是否存在相同的值array_unique

    有时候我们需要检查一个数组中是否存在重复的值。在这种情况下,`array_unique` 函数就能派上用场。`array_unique` 是PHP内建的一个非常实用的函数,它用于移除数组中的重复元素,从而创建一个新的数组,新数组中的...

    找出数组3个数字相加为0的组合

    排序后,我们可以使用两个指针,分别从数组的头部(较小的元素)和尾部(较大的元素)开始,每次迭代时计算当前两个指针所指向元素的和。如果这个和等于目标值(即0),则找到了一个满足条件的三元组;如果和小于...

    php判断数组中是否存在指定键(key)的方法

    在这个示例中,我们同样定义了一个数组,并通过isset函数检查了两个键名是否存在。由于"Two"键对应的值为null,因此isset返回false;而"2"键虽然数字键名是整数,但没有对应的值,所以isset同样返回false。 总结来...

    vue实现将一个数组内的相同数据进行合并

    2. 创建两个数组`contrast_1`和`contrast_2`,其中`contrast_1`是经过四舍五入处理后的订单列表副本,`contrast_2`是用于比对的数组副本。 3. 创建一个空数组`containers`用于存放合并后的订单数据。 4. 遍历`...

    基于C++,写一个程序 要求用户输入10个数据到数组中,然后将数组中最大值和最小值显示出来,并显示下标

    为了找到最大值和最小值,我们可以初始化两个变量,分别作为当前的最大值和最小值,并设定初始值为数组的第一个元素。然后再次遍历数组,与当前最大值和最小值进行比较,如果找到更大的值就更新最大值,找到更小的值...

    JS实现快速比较两个字符串中包含有相同数字的方法

    如果排序后的字符串相等,则说明两个数组包含相同的数字(顺序不同)。 5. 弹窗提示:使用alert方法来提示用户两个字符串中包含的数字是相同还是不同。 6. 在线工具的推荐:文中提到了一款在线文本比较工具,这...

    Lua检测数组(tabble)中是否包含某个值

    这个功能在很多实际应用中都非常有用,例如当需要快速判断某个元素是否存在于集合中时。 #### 方法一:遍历数组 最简单的方法是通过遍历整个表来查找指定的值。下面是一个示例函数`IsInTable`,用于检查一个给定的...

Global site tag (gtag.js) - Google Analytics