成人做爰A片免费播放乱码 ,美女扒开尿口让男人桶,日本色情免费视频,又黄又爽无遮挡,doi在线观看,97免费超碰,国产在线最新地址,一级欧美黄

算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎(chǔ)知識和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選！

今天和大家聊的問題叫做?搜索二維矩陣，我們先來看題面：

https://leetcode-cn.com/problems/search-a-2d-matrix/

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.

題意

編寫一個高效的算法來判斷 m x n 矩陣中，是否存在一個目標值。該矩陣具有如下特性：

每行中的整數(shù)從左到右按升序排列。

每行的第一個整數(shù)大于前一行的最后一個整數(shù)。

樣例

解題

https://www.cnblogs.com/techflow/p/13042496.html

這題剛拿到手可能會有些蒙，我們當然很容易可以看出來這是一個二分的問題，但是我們之前做的二分都是在一個一維的數(shù)組上，現(xiàn)在的數(shù)據(jù)是二維的，我們怎么二分呢？

我們仔細閱讀一下題意，再觀察一下樣例，很容易發(fā)現(xiàn)，如果一個二維數(shù)組滿足每一行和每一列都有序，并且保證每一行的第一個元素大于上一行的最后一個元素，那么如果我們把這個二維數(shù)組reshape到一維，它依然是有序的。

比如說有這樣一個二維數(shù)組：

[[1, 2, 3],
[4, 5, 6],
[7, 8, 9]]

它reshape成一維之后會變成這樣：[1, 2, 3, 4, 5, 6, 7, 8, 9]

reshape是numpy當中的說法，也可以簡單理解成把每一行串在一起。所以這題最簡單的做法就是把矩陣降維，變成一位的數(shù)組之后再通過二分法來判斷元素是否存在。如果偷懶的話可以用numpy來reshape，如果不會numpy的話，可以看下我之前關(guān)于numpy的教程，也可以自己用循環(huán)來處理。

reshape之后就是簡單的二分了，完全沒有任何難度：

class?Solution:
????def?searchMatrix(self, matrix: List[List[int]], target: int)?-> bool:
????????import?numpy as?np
????????arr = np.array(matrix)
????????# 通過numpy可以直接reshape
????????arr = arr.reshape((-1, ))
????????l, r = 0, arr.shape[0]
????????if?r == 0:
????????????return?False
????????# 套用二分
????????while?l+1?< r:
????????????m = (l + r) >> 1
????????????if?arr[m] <= target:
????????????????l = m
????????????else:
????????????????r = m
????????return?arr[l] == target

正經(jīng)做法

引入numpy reshape只是給大家提供一個解決的思路，這顯然不是一個很好的做法。那正確的方法應該是怎樣的呢？

還是需要我們對問題進行深入分析，正向思考感覺好像沒什么頭緒，我們可以反向思考。這也是解題常用的套路，假設(shè)我們已經(jīng)知道了target這個數(shù)字存在矩陣當中，并且它的行號是i，列號是j。那么根據(jù)題目當中的條件，我們能夠得出什么結(jié)論呢？

我們分析一下元素的大小關(guān)系，可以得出行號小于i的所有元素都小于它，行號大于i的所有元素都大于它。同行的元素列號小于j的元素小于它，列號大于j的元素大于它。

也就是說，行號i就是一條隱形的分界線，將matrix分成了兩個部分，i上面的小于target，i下方的大于target。所以我們能不能通過二分找到這個i呢？

想到這里就很簡單了，我們可以通過每行的最后一個元素來找到i。對于一個二維數(shù)組而言，每行的最后一個元素連起來就是一個一維的數(shù)組，就可以很簡單地進行二分了。

找到了行號i之后，我們再如法炮制，在i行當中進行二分來查找j的位置。找到了之后，再判斷matrix[i][j]是否等于target，如果相等，那么說明元素在矩陣當中。

整個的思路應該很好理解，但是實現(xiàn)的時候有一個小小的問題，就是我們查找行的時候，找的是大于等于target的第一行的位置。也就是說我們查找的是右端點，那么二分的時候維護的是一個左開右閉的區(qū)間。在邊界的處理上和平常使用的左閉右開的寫法相反，注意了這點，就可以很順利地實現(xiàn)算法了：

class?Solution:
????def?searchMatrix(self, matrix: List[List[int]], target: int)?-> bool:
????????n = len(matrix)
????????if?n == 0:
????????????return?False
????????
????????m = len(matrix[0])
????????if?m == 0:
????????????return?False
????????
????????# 初始化，左開右閉，所以設(shè)置成-1， n-1
????????l, r = -1, n-1
????????
????????while?l+1?< r:
????????????mid = (l + r) >> 1
????????????# 小于target的時候移動左邊界
????????????if?matrix[mid][m-1] < target:
????????????????l = mid
????????????else:
????????????????r = mid
????????????????
????????row = r
????????
????????# 正常的左閉右開的二分
????????l, r = 0, m
????????
????????while?l+1?< r:
????????????mid = (l + r) >> 1
????????????if?matrix[row][mid] <= target:
????????????????l = mid
????????????else:
????????????????r = mid
????????????????
????????return?matrix[row][l] == target

我們用了兩次二分，查找到了結(jié)果，每一次二分都是一個O(logN)的算法，所以整體也是log級的算法。

優(yōu)化

上面的算法沒有問題，但是我們進行了兩次二分，感覺有些麻煩，能不能減少一次，只使用一次二分呢？

如果想要只使用一次二分就找到答案，也就是說我們能找到某個方法來切分整個數(shù)組，并且切分出來的數(shù)組也存在大小關(guān)系。這個條件是使用二分的基礎(chǔ)，必須要滿足。

我們很容易在數(shù)組當中找到這樣的切分屬性，就是元素的位置。在矩陣元素的問題當中，我們經(jīng)常用到的一種方法就是對矩陣當中的元素進行編號。比如說一個點處于i行j列，那么它的編號就是i * m + j，這里的m是每行的元素個數(shù)。這個編號其實就是將二維數(shù)組壓縮到一維之后元素的下標。

我們可以直接對這個編號進行二分，編號的取值范圍是確定的，是[0, mn)。我們有了編號之后，可以還原出它的行號和列號。而且根據(jù)題目中的信息，我們可以確定這個矩陣當中的元素按照編號也存在遞增順序。所以我們可以大膽地使用二分了：

class?Solution:
????def?searchMatrix(self, matrix: List[List[int]], target: int)?-> bool:
????????n = len(matrix)
????????if?n == 0:
????????????return?False
????????
????????m = len(matrix[0])
????????if?m == 0:
????????????return?False
????????
????????l, r = 0, m*n
????????
????????while?l+1?< r:
????????????mid = (l + r) >> 1
????????????# 還原行號和列號
????????????x, y = mid // m, mid % m
????????????if?matrix[x][y] <= target:
????????????????l = mid
????????????else:
????????????????r = mid
????????return?matrix[l // m][l % m] == target