java 解法, 执行用时: 0 ms, 内存消耗: 64.6 MB, 提交时间: 2023-10-17 13:41:23

class Solution {
    public int smallestCommonElement(int[][] mat) {
        return found(mat, 0, 0);
    }

    public int found(int[][] mat, int x, int y){
        int sl = mat[0].length;
        for(int i = 0; i < mat.length; i++){
            if(i == x){
                continue;
            }
            int[] check = bf(mat[i], mat[x][y]);
            if(check[0] == 1){
                continue;
            }
            //目标数字未找到，而且数组都比目标小
            if(check[1] == sl){
                return -1;
            }
            //选取比当前数字大且距离最近的数字，继续判断
            //数组是递增的，且是其他数字从小到大开始遍历，当前不匹配，说明新数字前面较小数字也一定不匹配，直接跳过
            return found(mat, i, check[1]);
        }
        return mat[x][y];
    }

    public int[] bf(int[] arr, int target){
        int l = 0, r = arr.length - 1;
        while(l <= r){
            int mid = l + (r - l)/2;
            if(arr[mid] == target){
                return new int[]{1, mid};
            }
            if(arr[mid] > target){
                r = mid - 1;
            }else {
                l = mid + 1;
            }
        }
        return new int[]{0, l, r};
    }
}

cpp 解法, 执行用时: 52 ms, 内存消耗: 24 MB, 提交时间: 2023-10-17 13:40:30

class Solution {
public:
    int smallestCommonElement1(vector<vector<int>>& mat) {
        int count[10001] = {};
        const int m = (int)mat.size(), n = (int)mat[0].size();
        for (int j=0; j<n; ++j) {
            for (int i=0; i<m; ++i) {
                if (++count[mat[i][j]] == m) {
                    return mat[i][j];
                }
            }
        }
        return -1;
    }
    
    // 二分
    int smallestCommonElement2(vector<vector<int>>& mat) {
        const int m = (int)mat.size(), n = (int)mat[0].size();
        for (int j=0; j<n; ++j) {
            bool found = true;
            for (int i = 1; i < m && found; ++i) {
                found = binary_search(mat[i].begin(), mat[i].end(), mat[0][j]);
            }
            if (found) {
                return mat[0][j];
            }
        }
        return -1;
    }

    // 蓝红二分
    int smallestCommonElement(vector<vector<int>>& mat) {
        const int m = (int)mat.size(), n = (int)mat[0].size();
        vector<int>ls(m,-1);
        int r = n;
        for (int j=0; j<n; ++j) {
            bool found = true;
            for (int i = 1; i < m && found; ++i) {
                r = n;
                bool flag = false;
                while (ls[i]+1 != r) {
                    int mid = (ls[i]+r)>>1;
                    if (mat[i][mid] == mat[0][j]) {
                        flag = true;
                        break;
                    } else if (mat[i][mid] < mat[0][j]) {
                        ls[i] = mid;
                    } else {
                        r = mid;
                    }
                }
                found = flag;
            }
            if (found) {
                return mat[0][j];
            }
        }
        return -1;
    }
};

python3 解法, 执行用时: 52 ms, 内存消耗: 37.8 MB, 提交时间: 2023-10-17 13:37:53

class Solution:
    # 逐行查找
    def smallestCommonElement1(self, mat: List[List[int]]) -> int:
        if not mat:
            return -1
        n = len(mat)
        counts = collections.defaultdict(int)
        for nums in mat:
            for val in nums:
                counts[val] += 1
        for k,v in counts.items():
            if v == n:
                return k
        return -1
        
    # 二分查找
    def smallestCommonElement(self, mat: List[List[int]]) -> int:
        '''
        通过二分查找，顺序判断矩阵的公共最小值
        '''
        if not mat:
            return -1
        n, m = len(mat), len(mat[0])

        def bisect_right(nums, val):
            '''二分查找，返回数组中大于等于val的值，如果val为最大返回None'''
            if not nums:
                return
            m = len(nums)
            l, r = 0, m - 1
            while l <= r:
                mid = (r - l) // 2 + l
                if val == nums[mid]:
                    return val
                if val < nums[mid]:
                    r = mid - 1
                else:
                    l = mid + 1
            return nums[l] if l < m else None

        '''矩阵左上角的为最小值，match为匹配的行数，cur_row为滚动匹配的行'''
        base = mat[0][0]
        match = 0
        cur_row = 1
        while match <= m:
            val = bisect_right(mat[cur_row % n], base)
            if not val:
                return -1
            elif val != base:
                base = val
                match = 1
            elif match == m:
                return val
            cur_row += 1
            match += 1

        return -1

golang 解法, 执行用时: 68 ms, 内存消耗: 10.4 MB, 提交时间: 2023-10-17 13:35:33

func smallestCommonElement(mat [][]int) int {
    cnt := map[int]int{}
    n, m := len(mat), len(mat[0])
    for i:=0;i<n;i++{
        for j:=0;j<m;j++{
            cnt[mat[i][j]]++
        }
    }
    for k,v := range cnt{
        if v == n {
            return k
        }
    }
    return -1
}