1351. Count Negative Numbers in a Sorted Matrix

題目連結: Leetcode

題目概要

給一

$n\times m$ 的已排序陣列
輸出共有多少個負數

想法

法一 暴力解

迭代每一個數值
每迭代到一個負數就紀錄

法二 二分搜

針對每列陣列做二分搜尋,找到負數的開頭索引值

法三 線性搜尋

因陣列的負數在整個

$n\times m$集中在右下測
且每列皆已排序

因此可從每列的後方開始尋找負數的開頭索引值
找到一列的值後紀錄該列的負數數量
再往下一列的同個索引值開始向左尋找
直到索引值

$<$ 0

參考解法

歡迎補充

CPP 暴力解

int countNegatives(vector<vector<int>>& grid) {
    int ans = 0;
    for (int i=0; i<grid.size(); i++){
        for (int j=0; j<grid[0].size(); j++){
            if (grid[i][j] < 0) ans++;
        }
    }
    return ans;
}

CPP 二分搜

int countNegatives(vector<vector<int>>& grid) {
    int ans = 0,
        n = grid[0].size();

    for (auto r: grid){
        int left = 0, right = n-1, mid;
        while (left <= right){
            mid = (left + right) / 2;
            if (r[mid] < 0) right = mid -1;
            else left = mid +1;
        }
        ans += n - left;
    }
    return ans;
}

CPP 線性搜

int countNegatives(vector<vector<int>>& grid) {
    int ans = 0,
        n = grid[0].size(),
        index = n - 1;
    for (auto r: grid){
        while (index >= 0 and r[index] < 0){
            index--;
        }
        ans += n - (index + 1);
    }
    return ans;
}