【劍指offer】1.二維數組查找

wawor4827 發布于2019-08-23 14:32 / 1613人閱讀

摘要：題目在一個二維數組中每個一維數組的長度相同，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數，輸入這樣的一個二維數組和一個整數，判斷數組中是否含有該整數。

題目

在一個二維數組中（每個一維數組的長度相同），每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數，輸入這樣的一個二維數組和一個整數，判斷數組中是否含有該整數。

基本思路

二維數組是有序的，比如下面的數據：

1 2 3
4 5 6
7 8 9

可以直接利用左下角數字開始查找：

大于：比較上移

小于：比較右移

代碼思路

將二維數組看作平面坐標系

從左下角（0,arr.length-1）開始比較：

目標值大于坐標值---x坐標+1

目標值小于坐標值---y坐標-1

注意：

二維數組arri中

j代表x坐標

i代表y坐標

代碼

    function Find(target, array) {
      let i = array.length - 1; // y坐標
      let j = 0; // x坐標
      return compare(target, array, i, j);
    }

    function compare(target, array, i, j) {
      if (array[i] === undefined || array[i][j] === undefined) {
        return false;
      }
      const temp = array[i][j];
      if (target === temp) {
        return true;
      }
      else if (target > temp) {
        return compare(target, array, i, j+1);
      }
      else if (target < temp) {
        return compare(target, array, i-1, j);
      }
    }

拓展：二分查找

二分查找的條件是必須有序。

和線性表的中點值進行比較，如果小就繼續在小的序列中查找，如此遞歸直到找到相同的值。

    function binarySearch(data, arr, start, end) {
        if (start > end) {
            return -1;
        }
        var mid = Math.floor((end + start) / 2);
        if (data == arr[mid]) {
            return mid;
        } else if (data < arr[mid]) {
            return binarySearch(data, arr, start, mid - 1);
        } else {
            return binarySearch(data, arr, mid + 1, end);
        }
    }

云服務器 GPU云服務器數組查找數組java二維數組二維數組轉換一維數組一維數組和二維數組

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/100763.html

劍指offer(javascript版)

摘要：二維數組中的查找在一個二維數組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數，輸入這樣的一個二維數組和一個整數，判斷數組中是否含有該整數。例如輸入前序遍歷序列和中序遍歷序列，則重建二叉樹并返回。 1.二維數組中的查找在一個二維數組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數，輸入這樣的一個二維數...

imtianx 2019-08-20 15:20 評論0 收藏0
劍指offer中的算法題(PHP版)

摘要：二維數組中的查找在一個二維數組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。解法有兩種，一種是遞歸法，一種是迭代法但是遞歸法計算的時間復雜度是以的指數的方式遞增的，如果面試中千萬不要用遞歸法，一定要用迭代法。二維數組中的查找在一個二維數組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數，輸入這樣的一個二維數組和...

big_cat 2019-06-27 15:43 評論0 收藏0
劍指Offer(Java版) 持續更新中

摘要：面試題從尾到頭打印鏈表輸入一個鏈表，從尾到頭打印鏈表每個節點的值面試題重建二叉樹輸入某二叉樹的前序遍歷和中序遍歷的結果，請重建出該二叉樹。例如輸入前序遍歷序列和中序遍歷序列，則重建二叉樹并返回。隊列中的元素為類型。其中負數用補碼表示。面試題2 單例(之前有整理，略) 面試題3 二維數組中的查找 public boolean find(int target, int [][] arra...

justCoding 2019-08-15 11:04 評論0 收藏0
LeetCode 精選TOP面試題【51 ~ 100】

摘要：有效三角形的個數雙指針最暴力的方法應該是三重循環枚舉三個數字。總結本題和三數之和很像，都是三個數加和為某一個值。所以我們可以使用歸并排序來解決這個問題。注意因為歸并排序需要遞歸，所以空間復雜度為 ...

Clect 2021-11-15 11:38 評論0 收藏0