打印唯一的行号。
以下是我的实现:
#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(行*列);因为每一行然后每一列元素都会被访问。
这是最佳运行时间吗?
最佳答案
你的方法似乎有问题:
函数
rowsToInt
转换 5int
的子数组为0
之间的值和31
假设这些值严格是二进制(0 或 1)。在函数
removeDuplicates
中,您可以使用这些值作为表达式中的移位计数器:(mask << (value-1))
哪里mask
是int
值(value)1
。这是一种跟踪迄今为止看到的行的巧妙方法,但该表达式会调用value == 0
的未定义行为。 .
您应该使用 unsigned long
解决此问题输入 tracker
,保证至少有 32 位,并且 (1UL << value)
值 0
的定义和不同至31
.
复杂度确实是O(rows * 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;
}
关于c++ - 查找二进制二维数组中的唯一行,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/38556583/