Merge pull request 6boris#86 from kylesliu/develop

6boris · web-flow · commit 78b9574ece41 · 2019-09-17T20:56:26.000+08:00
add  the 74 problem solution
diff --git a/src/0074.Search-a-2D-Matrix/README.md b/src/0074.Search-a-2D-Matrix/README.md
@@ -23,21 +23,36 @@ Output: "10101"
 **Tags:** Math, String
 
 ## 题意
->给你两个二进制串，求其和的二进制串。
+>写一个高效算法，在矩阵中查找一个数是否存在。矩阵有如下特点：
+- 矩阵中每行的数，从左到右单调递增；
+- 每行行首的数大于上一行行尾的数；
 
 ## 题解
 
 ### 思路1
-> 按照小学算数那么来做，用 `carry` 表示进位，从后往前算，依次往前，每算出一位就插入到最前面即可，直到把两个二进制串都遍历完即可。
+> 我们可以想象把整个矩阵，按行展开成一个一维数组，那么这个一维数组单调递增，然后直接二分即可。
+  二分时可以通过整除和取模运算得到二维数组的坐标。
+  时间复杂度分析：二分的时间复杂度是 O(logn2)=O(logn)O(logn2)=O(logn)。
 
-```go
-
-```
 
-### 思路2
-> 思路2
 ```go
-
+func searchMatrix(matrix [][]int, target int) bool {
+	if len(matrix) == 0 {
+		return false
+	}
+	n, m := len(matrix), len(matrix[0])
+	l, r := 0, n*m-1
+
+	for l < r {
+		mid := (l + r) / 2
+		if matrix[mid/m][mid%m] >= target {
+			r = mid
+		} else {
+			l = mid + 1
+		}
+	}
+	return matrix[r/m][r%m] == target
+}
 ```
 
 ## 结语
diff --git a/src/0074.Search-a-2D-Matrix/Solution.go b/src/0074.Search-a-2D-Matrix/Solution.go
@@ -1,5 +1,19 @@
 package Solution
 
-func Solution(x bool) bool {
-	return x
+func searchMatrix(matrix [][]int, target int) bool {
+	if len(matrix) == 0 {
+		return false
+	}
+	n, m := len(matrix), len(matrix[0])
+	l, r := 0, n*m-1
+
+	for l < r {
+		mid := (l + r) / 2
+		if matrix[mid/m][mid%m] >= target {
+			r = mid
+		} else {
+			l = mid + 1
+		}
+	}
+	return matrix[r/m][r%m] == target
 }
diff --git a/src/0074.Search-a-2D-Matrix/Solution_test.go b/src/0074.Search-a-2D-Matrix/Solution_test.go
@@ -2,28 +2,37 @@ package Solution
 
 import (
 	"reflect"
+	"strconv"
 	"testing"
 )
 
 func TestSolution(t *testing.T) {
 	//	测试用例
 	cases := []struct {
 		name   string
-		inputs bool
+		matrix [][]int
+		target int
 		expect bool
 	}{
-		{"TestCacse 1", true, true},
-		{"TestCacse 1", true, true},
-		{"TestCacse 1", false, false},
+		{"TestCase", [][]int{
+			{1, 3, 5, 7},
+			{10, 11, 16, 20},
+			{23, 30, 34, 50},
+		}, 3, true},
+		{"TestCase", [][]int{
+			{1, 3, 5, 7},
+			{10, 13, 16, 20},
+			{23, 30, 34, 50},
+		}, 13, true},
 	}
 
 	//	开始测试
-	for _, c := range cases {
-		t.Run(c.name, func(t *testing.T) {
-			ret := Solution(c.inputs)
-			if !reflect.DeepEqual(ret, c.expect) {
+	for i, c := range cases {
+		t.Run(c.name+" "+strconv.Itoa(i), func(t *testing.T) {
+			got := searchMatrix(c.matrix, c.target)
+			if !reflect.DeepEqual(got, c.expect) {
 				t.Fatalf("expected: %v, but got: %v, with inputs: %v",
-					c.expect, ret, c.inputs)
+					c.expect, got, c.matrix)
 			}
 		})
 	}
