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

标签 c++ arrays matrix multidimensional-array

打印唯一的行号。

以下是我的实现:

#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转换 5 int 的子数组为 0 之间的值和31假设这些值严格是二进制(0 或 1)。

  • 在函数 removeDuplicates 中,您可以使用这些值作为表达式中的移位计数器:(mask << (value-1))哪里maskint值(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/

相关文章:

c++ - 构建 XPCOM XULRunner 2.0 或更新版本

c - 在结构中使用字符串

arrays - 在给定的整数数组中找到一个以偶数频率出现的单个整数,而所有其他整数以奇数频率出现

Java - 2 float 类型的数组 - 发现可能存在精度损失 : float required : int

c - C 中相反方向的对角矩阵

c++ - 模板类方法的部分特化或实例化

C++ SDL2 程序在切换循环时崩溃

c++ - std::map::emplace() 缺失 - 过时的库?

android - Android 平板电脑随机调整大小问题

java - 如何快速获取图像矩阵? java