c++ - 如何在二维数组中使用二进制搜索?

标签 c++ arrays data-structures binary-search quicksort

我想在 C++ 中比较 2 个二维数组(某些特定元素)arr1[][],arr[][],我正在使用for 循环来比较它们但是花了很长时间。

我可以使用搜索算法来实现它,例如二进制搜索或快速搜索吗?我该如何实现?

到目前为止,这是我的代码:

for (k = 0; k < MAXROW; k++)
{  
  for (m = 0; m <  MAXROW; m++)
   {
     for(j=0;j<MAXCOL;j++)
     {
        if(arr[k][3] ==arr1[m][3]) 
        {
          if((arr[k][1] ==arr1[m][1] && arr[k][2] ==arr1[m][2]))
          {
             cout<<" \n same element";
          }
          else
             cout<<"\n inner  different elements";
        }
        else
           cout<<"\n different elements";

最佳答案

判断两个二维数组是否相等(在不知道其组织结构的情况下)的唯一方法是比较每个元素。这应该有 O(mn) 运行时间,其中 m=# of rows 和 n=# of columns。您似乎编写了一个额外的循环,这可能就是您认为它运行太慢的原因。以下是我将如何编写比较:

bool are_equal = true;
for (int i = 0; i < MAX_ROWS; ++i) {
  for (int j = 0; j < MAX_COLS; ++j) {
    if (arr1[i][j] != arr2[i][j]) {
      are_equal = false;
      break;
    }
  }
}
if (are_equal) {
  std::cout << "The arrays are equal." << std::endl;
} else {
  std::cout << "The arrays differ by at least one element." << std::endl;
}

仅比较第 3 列和第 4 列(或列的任何子集):

int columns_to_check[] = {2, 3}; // Remember that these are 0-indexed
const int NUM_COLS = sizeof(columns_to_check)/sizeof(int);

bool are_equal = true;
for (int i = 0; i < MAX_ROWS; ++i) {
  for (int j = 0; j < NUM_COLS; ++j) {
    int col = columns_to_check[j];
    if (arr1[i][col] != arr2[i][col]) {
      are_equal = false;
      break;
    }
  }
}
if (are_equal) {
  std::cout << "The arrays are equal." << std::endl;
} else {
  std::cout << "The arrays differ by at least one element." << std::endl;
}

关于c++ - 如何在二维数组中使用二进制搜索?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10345130/

相关文章:

C++ - 返回 const unique_ptr

javascript - 如何在 javascript 中创建一个包含长度为 x 的数字字符串的数组?

java - 为什么通过 stream() 调用比使用 if 子句更耗时?

java - 如何从 Trie 中检索给定长度的随机单词

php - 什么时候应该在不指定键的情况下对数组使用 isset()?

data-structures - 将排序数组转换为 2-4 B 树的复杂性

c++ - 计算程序的运行时间(大 O 表示法)

c++ - std::stof 是解析整个字符串还是在第一个空格/换行符处停止?

c++ - 上交所加成产生垃圾

c# - 如何将字符串数组转为int数组进行计算?