1198. Find Smallest Common Element in All Rows

要找出每個列中都有的值, 倘若有兩個以上的值符合, 我們回傳最小的值

最慢的方法是遍歷整個矩陣, 然後count所以數值, 一旦有存在跟row一樣數量數量, 我們就記錄起來, 然後找到最小值就回傳, 沒有這個數字的話我們就回傳-1

class Solution {
public:
  int smallestCommonElement(vector<vector<int>> &mat) {
    unordered_map<int, int> m;
    int r = mat.size();
    int c = mat[0].size();
    if(c == 0 || r == 0) return -1;
    for(int i = 0 ; i < r;i++){
      for(int j = 0; j < c; j++){
        m[mat[i][j]]++;
      }
    }
    int s = INT_MAX;
    for(auto i : m){
      if(i.second == r && i.first < s){
        s = i.first;
      }
    }
    return s == INT_MAX? -1:s;
  }
};

但這個時間複雜度是O(n²), 看有沒有辦法在縮減

由於每列都嚴格遞增, 我想到一種用binary search的方式

我們先看第一列有多少元素, 並把這些元素記錄下來, 接著我們在每一列找這些元素, 都用二分搜尋法找, 找不到即可中斷,

這樣一來時間複雜度可以縮到O(c * r * logc)

class Solution {
public:
  static bool bs(vector<int> &arr, int target){
    int l = 0;
    int r = arr.size() -1;
    while( l <= r){
      int mid = (l + r) / 2;
      if(arr[mid] == target){
        return true;
      }else if(arr[mid] < target){
        l = mid + 1;
      }else{
        r = mid - 1;
      }
    }
    return false;
  }
  int smallestCommonElement(vector<vector<int>> &mat) {
    unordered_set<int> st;
    int r = mat.size();
    int c = mat[0].size();
    if(c == 0 || r == 0) return -1;
    for(int j = 0; j < c;j++){
      st.insert(mat[0][j]);
    }
    int res = INT_MAX;
    for(auto e: st){
      int number = 1;
      for(int i = 1 ; i < r;i++){
        if(bs(mat[i], e)){
          number++;
        }else{
          break;
        }
      }
      if(number == r && e < res){
        res = e;
      }
    }
    return res == INT_MAX? -1:res;
  }
};