查找二进制二维数组中的唯一行

Question

打印唯一的行号。

以下是我的实现：

#include <iostream> 
#include <cmath> 

int rowsToInt(int m[][5], int row, int cloumLen) { 
    int sum = 0; 
    // m[row][column] 
    for (int i = 0; i < cloumLen; i++) { 
     sum += m[row][i]*(std::pow(2,i)); 
    } 
    return sum; 
} 

void removeDuplicate(int m[][5], int row, int column) { 
    if (!m) { 
     return; 
    } 

    int tracker = 0; 
    int mask = 1; 
    int value; 

    for (int i = 0; i < row; i++) { 
     value = rowsToInt(m, i, column); // 3 
     if (((mask << (value - 1)) & tracker) == 0) { 
      // print unique row 
      std::cout << "row: " << i << " is unique" << std::endl; 

      // set that bit to 1 
      tracker = tracker^(mask << (value - 1)); 
     } 
    } 
} 

int main() { 
    int array[5][5] = { 
     {0,1,0,0,1}, 
     {1,0,1,1,0}, 
     {0,1,0,0,1}, 
     {1,1,1,0,0}, 
     {1,1,0,1,1} 
    }; 
    removeDuplicate(array, 5, 5); 
    return 0; 
} 

输出为：

row: 0 is unique 
row: 1 is unique 
row: 3 is unique 
row: 4 is unique 

什么是运行时间？我认为它的O（行*列）;因为每一行然后是每个列元素都被访问。

这是最优化的运行时间吗？

Answer 1

在代码中最慢的部分是std::pow()，与20万行，它会被称为是需要大量的时间一个百万次阵列，所以不要用它在没有必要的循环中。如果你需要2的幂，最快的方法是使用按位旋转，就像@chqrlie一样。一般来说，如果您需要N的电源，您可以按如下方式获取它们：

int rowsToInt (bool m[][5], int row, int cloumLen) { 
    int sum = 0; 
    for (int i = 0, p = 1; i < cloumLen; i++) { 
     sum += m[row][i]*p; 
     p *= N; 
    } 
    return sum;  
} 

现在进行优化。如果你使用二进制矩阵，你为什么使用整数？它需要4倍的RAM，所以使用bool array[rows][cols]。行数和列数是常数，所以不需要将它们传递给函数。您可以声明全球const int rows = 7, cols = 5。还有一个重要因素。如果您在大矩阵中搜索唯一的二进制行，则值得对已发现的行进行计数。如果你已经找到了2^cols，就离开循环。

您的搜索方法相当复杂。让我展示两种更简单的方法来解决您的问题。

更紧凑的方式：

// the code inside removeDuplicate function 
unsigned long tracker = 0; // now it looks like 32 zeros 
for (int i = 0; i < row; ++i) { 
    int value = rowsToInt (m, i, column); // getting dec value 

    if (((tracker >> value) & 1) == 0) { // if the valueth bit is equal to zero 
     tracker |= (1UL << value); // set it equal to one 
     std::cout << "row: " << i << " is unique" << std::endl; 
     if (tracker = 0xffffffff) return; // if all bits are equal to 1, we've found all the unique rows 
    } 
} 

和最简单的一个：

// the code inside removeDuplicate function 
bool found[32] = {false}; // using array instead of UL 
int counter = 0; // and simple counter of unique rows 

for (int i = 0; i < row; i++) { 
    int value = rowsToInt (m, i, column); // getting dec value 

    if (!found[value]) { // if the valueth element is equal to zero 
     found[value] = true; // set it equal to one 
     ++counter; // and increase the counter 
     std::cout << "row: " << i << " is unique" << std::endl; 
     if (counter == 32) return; 
    } 
} 

Answer 2

你的方法似乎有一个问题：

• 功能rowsToInt的5 int子阵列转换为0和31假设之间的值这些值是严格的二进制（0或1）。

• 在功能removeDuplicates，你在表达式中使用这些值作为移位计数器：(mask << (value-1))其中mask为int与值1。跟踪迄今为止所看到的行是一种精明的方式，但表达式会调用value == 0的未定义行为。

您应该使用固定型unsigned long为tracker此问题，保证具有至少32位，并(1UL << value)定义和值0到31不同。

的复杂性确实O（行*的cols），但是算法固有限制为cols <= 5，所以很难谈的复杂性时cols不能随意增加。

此外，使用pow(2, i)计算二进制值的效率非常低。

下面是一个简单的版本：

#include <iostream> 
#include <cmath> 

int rowsToInt(int m[][5], int row, int cloumLen) { 
    int sum = 0; 
    // m[row][column] 
    for (int i = 0; i < cloumLen; i++) { 
     sum += m[row][i] << i; 
    } 
    return sum; 
} 

void removeDuplicate(int m[][5], int row, int column) { 
    if (!m) { 
     return; 
    } 

    unsigned long tracker = 0; 

    for (int i = 0; i < row; i++) { 
     int value = rowsToInt(m, i, column); // 3 
     if (((1UL << value) & tracker) == 0) { 
      // print unique row 
      std::cout << "row: " << i << " is unique" << std::endl; 
      // set that bit to 1 
      tracker |= 1UL << value;   
     } 
    } 
} 

int main() { 
    int array[7][5] = { 
     {0,1,0,0,1}, 
     {1,0,1,1,0}, 
     {0,1,0,0,1}, 
     {1,1,1,0,0}, 
     {1,1,0,1,1}, 
     {0,0,0,0,0}, 
     {0,0,0,0,0}, 
    }; 
    removeDuplicate(array, 7, 5); 
    return 0; 
}