• 欢迎光临~

杨氏矩阵

开发技术 开发技术 2022-07-24 次浏览

在一个行和列都是依次递增的矩阵(这里是二维数组)中,如何设计一个时间复杂度为O(n)的算法,判断矩阵中是否存在元素x?

int find_x(vector<vector<int>> &m,int x){
    // 列数
    int c = m[0].size()-1;
    // 行数
    int r = 0;
    // 遍历数据的个数   -- 用来测试复杂度
    int t = 0;
    while(c <= m.size()-1 && r >= 0){
        if (x == m[r][c])
            return t;
        if (x > m[r][c]){
            r++;
            t++;
        }
        if (x < m[r][c]){
            c--;
            t++;
        }
        if (c<0 || r >= m.size())
            break;
    }
    return 0;
}
程序员灯塔
转载请注明原文链接:杨氏矩阵
喜欢 (0)