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

Question

我有两个数组，分别是a[]和b[]。我想搜索 b 中是否存在 a 的任何元素。请注意，如果 a[] 中的任何一个元素存在于 b[] 中，我不想找到所有重复出现的地方，我想报告它并在不检查 a[] 或 b[][=11 的其余部分的情况下中断=]

我对 'break' 的运作方式有点困惑。 'break' 能否跳出任何类型的循环 - for/while，但它只能跳出它在代码中放置的位置附近的 'innermost loop'？

这是我的解决方案，如果这个 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

break 仅中断使用它的最内层循环。如果你想避免丑陋的语法，那么你有多种解决方案：

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

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

Answer 2

您可以按照此处所述使用 goto How to break out of nested loops? 这是最后剩余的有效用法...

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

虽然复杂...

Answer 3

breaks 通常会跳出 c 中最内层的循环。你用对了。

如果您只想报告重复项，那么您可以将此代码放入一个函数中，只要发现重复项，您就可以 return。该函数如下所示：

//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 中的每个元素进行二分查找，从而提高该算法的效率。

伪代码是这样的：

//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 是正确的

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

look for only the first common element between two arrays

c

break

duplicate-removal