查找二進制二維數組中的唯一行

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; 
}