只查找两个数组之间的第一个公共元素

Question

我有两个数组，即a[]和b[]。我想搜索b中是否存在a的任何元素。请注意，我不希望找到所有重复的事件，如果a[]中的任何一个元素存在于b[]中，我想报告它，并在不检查a[]或b[]的其余部分的情况下进行分解。

我有点搞不懂“休息”是怎么运作的。“中断”可以突破任何类型的循环-for/ the，但它只会突破放置在代码中的“最内部循环”？

这是我的解决方案，请建议这种O(n^2)方法是否有更好的实现

#include <stdio.h>

int main(void)
{
 int a[] = {1,2,3,4,5,6};
 int b[] = {11,2,3,7,8,9,6,10,11};
 int i = 0, j = 0;
 int duplicate = 0;

 for(i=0;i<sizeof(a)/sizeof(int);i++)
 {
  for(j=0;j<sizeof(b)/sizeof(int);j++)
  {
   if(a[i] == b[j])
   {
    printf("Duplicates found for [%d]\n",a[i]);
    duplicate = 1;
    break;
   }
  }

  if(duplicate == 1)
  {
   break;
  }
 }

 return 0;
}

Answer 1

中断通常会从c中最内部的循环中分离出来。您已经正确地使用了它。

如果您只想报告一个副本，那么您可以将此代码放入一个函数中，每当发现一个副本时，您只需返回。该函数如下所示：

//Here a and b are pointers to array 
//n1 and n2 are number of elements in array a,b
chk_dup(int *a,int *b,int n1,,int n2){

for(i=0;i<n1;i++)
 {
  for(j=0;j<n2;j++)
  {
   if(a[i] == b[j])
   {
    printf("Duplicates found for [%d]\n",a[i]);
    //duplicate = 1;
    //break;
    return;
   }
  }
 }
}

您不能在这里使用sizeof(a)，因为它只是一个指向array.Same的指针，代表了sizeof(b)。

您可以通过使用快速排序(使用O(nlgn))对数组进行排序，然后对b中的do二进制搜索中的每个元素进行排序，从而使该算法更有效。

该代码的伪代码如下所示：

//Here a and b are pointers to sorted arrays 
//n1 and n2 are number of elements in array a,b
chk_dup(int *a,int *b,int n1,,int n2){

for(i=0;i<n1;i++)
 {
   //find a[i] in b using binary search.
   int found=binary_search(a[i],b);
   if(found){
     printf("Found Duplicate");
     return;
   }
 }
 printf("No duplicate found");
}

因此，整个算法工作在O(nlgn)中。而您所使用的算法可以取O(n^2)。

否则，您的代码是非常好的，并且使用了break是正确的。

Answer 2

break只中断使用它的最内部循环。如果您想避免丑陋的语法，那么您有多个解决方案：

• 忽略这个优化，直到你证明它是相关的
• 将代码移到接受这两个数组作为参数的函数中，这样您就可以直接从函数中return而不必中断。
• 调整索引i和j之后，您发现了一个副本，以使两个循环优雅地返回。
• 使用goto指令(在任何情况下都不可取)

其他复杂度低于O(n^2)的解决方案可能需要一些额外的数据结构，例如哈希集或数据排序。

Answer 3

您可以使用goto，如前所述，How to break out of nested loops?，这是最后一次有效使用.

也许有一个更好的解决方案使用xor，不确定您是否可以减少

但复杂性..。