伊莉討論區

標題: 一道經典的面試題：二維數組查找 [打印本頁]
作者: kym3    時間: 2014-5-15 07:05 PM     標題: 一道經典的面試題：二維數組查找

本帖最後由 kym3 於 2014-5-15 07:06 PM 編輯

這是一道關于二分查找的面試題。

有一個二維數組，每一行都是按從小到大的順序排列的，並且，第一行最大的數小于等于第二行最小的數，第二行最大的數小于等于第三行最小的數。


例如：
[1,   3,  5,  7],
[10, 11, 16, 20],
[23, 30, 34, 50]


每一行的長度未必相等。
然后要求寫一個C++程序，在這個二維數組中完成查找。

//找到就返回true，找不到就返回false。
bool searchMatrix(std::vector<std::vector<int> > &matrix, int target) ;

嗯。要不我過1天再公布答案？

我先給一個不合格的答案：
把這個矩陣的所有元素全部copy到一個新數組里，然后在這個新數組里進行二分查找。
說這個方案不合格是因為：
1. 它的算法復雜度是O(n),我要求比這個更小
2. 要求所需的額外空間與這個矩陣的規模無關。即空間復雜度為O(1)





補充內容 (2014-5-17 06:23 PM):
答案見9樓。
作者: snowflying    時間: 2014-5-15 10:45 PM

先二分搜第一維最小值或最大值 (最小值比較簡單)
然後在該行二分搜?
作者: kym3    時間: 2014-5-15 11:30 PM

snowflying 發表於 2014-5-15 10:45 PM
先二分搜第一維最小值或最大值 (最小值比較簡單)
然後在該行二分搜?

對。代碼怎麼寫呢？
這兩次二分的代碼略微有點不同。
作者: andrew33673367    時間: 2014-5-15 11:50 PM

snowflying 發表於 2014-5-15 10:45 PM
先二分搜第一維最小值或最大值 (最小值比較簡單)
然後在該行二分搜?

為甚麼不從第二維中間那行開始找??不是排好了嗎??
作者: snowflying    時間: 2014-5-16 12:11 AM

本帖最後由 snowflying 於 2014-5-16 01:31 AM 編輯
kym3 發表於 2014-5-15 11:30 PM
對。代碼怎麼寫呢？
這兩次二分的代碼略微有點不同。
  1. bool comp(const int val , vector<int> vc)
  2. {
  3.         return val < vc[0];
  4. }
  5. bool searchMatrix(vector<vector<int> > &matrix, const int target)
  6. {
  7.     vector<vector<int> >::iterator it;
  8.    
  9.     it = upper_bound(matrix.begin() , matrix.end() , target , comp);
  10.     --it;
  11.         
  12.     if(it < matrix.begin())
  13.         return false;

  15.     return binary_search(it->begin() , it->end() , target);
  16. }
複製代碼
也可改成
  1. it = upper_bound(matrix.begin() , matrix.end() , target , comp);

  3. if(it == matrix.begin())
  4.         return false;

  6. --it;
  7. return binary_search(it->begin() , it->end() , target);
複製代碼
作者: kym3    時間: 2014-5-16 01:52 PM

snowflying 發表於 2014-5-16 12:11 AM
也可改成

贊！

面試官可能繼續問：“假如不讓用upper_bound和binary_search這兩個函數呢？ 你能自己把這兩個函數實現一下嗎？”
作者: kym3    時間: 2014-5-16 01:53 PM

kym3 發表於 2014-5-15 11:30 PM
對。代碼怎麼寫呢？
這兩次二分的代碼略微有點不同。

const可以加在matrix上，加在target上沒有必要，開源代碼中很少有這麼寫的。
作者: kym3    時間: 2014-5-16 02:11 PM

本帖最後由 kym3 於 2014-5-16 02:12 PM 編輯
kym3 發表於 2014-5-16 01:53 PM
const可以加在matrix上，加在target上沒有必要，開源代碼中很少有這麼寫的。

因為T有可能是std::string，按引用傳遞可以減少copy。
比如你看string::substr

       basic_string substr (size_type __pos=0, size_type __n=npos) const


就不要const。因為確信知道size_type是整數類型，不會是復雜的復合類型。
作者: kym3    時間: 2014-5-17 06:18 PM

本帖最後由 kym3 於 2014-5-17 06:21 PM 編輯

    bool searchMatrix(vector<vector<int> > &matrix, int target) {
        size_t m=matrix.size();
        size_t begin=0;
        for(;m;m>>=1){
            size_t mid=begin+ (m>>1);
            if(matrix[mid][0]<=target){
                begin=mid+1;
                m--;
            }
        }
        if(begin==0) return false;
        begin--;
        std::vector<int>& v=matrix[begin];
        begin=0;
        m=v.size();
        for(;m;m>>=1){
            size_t mid=begin+(m>>1);
            if(v[mid]==target) return true;
            else if(v[mid]<target){
                begin=mid+1;
                m--;
            }
        }
        return false;
    }
總共由兩個二分查找組成。第一個先找到對應的行，第二個再在具体的行做二分查找。兩個二分查找最大的區別在于，第一個二分查找只有2個分支，第二個有3個分支。第二個雖然只有3個分支，但是卻需要涵蓋2x2+1=5種情況。即
1. 找到相等的了
2. 大于關鍵字，且數組的長度為奇數
3. 大于關鍵字，且數組的長度為偶數
4. 小于關鍵字，且數組的長度為奇數
5. 小于關鍵字，且數組的長度為偶數


代碼雖短，里面的邏輯思路卻值得慢慢回味。





歡迎光臨 伊莉討論區 (http://989.eyny.com/) Powered by Discuz!