未分類

Search a 2D Matrix II

BinarySearch, DivideAndConquer, Go, LeetCode

Search a 2D Matrix II

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 in ascending from left to right.
  • Integers in each column are sorted in ascending from top to bottom.

For example:

Consider the following matrix:

1
2
3
4
5
6
7
[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

Given target = 5, return true.

Given target = 20, return false.

Default:

1
2
3
func searchMatrix(matrix [][]int, target int) bool {
}

解答思路:

先前雖然有Search a 2D Matrix，不過當時不但右邊的元素一律比左邊大，而且下面整列的所有元素一律比上面的元素來的大，因此可以透過兩次二分法來推出目標值是落在x軸與y軸的哪個位置且是否存在，不過這次只能保證該元素的正下方比較大，所以只能從頭開始與鄰近的元素一一作比較並逐步靠進目標值，而唯一要注意的就是開始比較的位置，從最左上角開始的話，如果目標值比較大而需要往值大的地方移動時，往下或往右便成了問題，並且無法確保用最少的移動數到達目標值，但如果從最右上角開始的話所有的問題便都解決了，如果目標值比較大而需要往值大的地方移動時就只能往下移動(因為已經在最右邊了)，而如果目標值比較小而需要往值小的地方移動也就只能往左邊移動，如此一來就可以用最簡單的方式及最快的路徑到達目標值，最後當移動到超出二元陣列範圍外時便能確定此值不存在。

程式碼解說:

一開始先判斷二元陣列是否為空，如果是便直接回傳false，否則就先初始化二元陣列最右上角的位置，接著便以此做為起點逐步靠進目標值，如果元素值與目標值相等便回傳true，而如果元素值比目標值大便往左邊移動，元素值比目標值小便往下面移動，不斷重覆上述動作直到發現目標值為止，最後當移動到超出二元陣列範圍外時便能確定此值不存在回傳false

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
if len(matrix) == 0 {
	return false
}
var y int
var element int
x := len(matrix[0]) - 1
for x >= 0 && y < len(matrix) {
	element = matrix[y][x]
	if element == target {
		return true
	} else if element > target {
		x--
	} else {
		y++
	}
}
return false

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func searchMatrix(matrix [][]int, target int) bool {
	if len(matrix) == 0 {
		return false
	}
	var y int
	var element int
	x := len(matrix[0]) - 1
	for x >= 0 && y < len(matrix) {
		element = matrix[y][x]
		if element == target {
			return true
		} else if element > target {
			x--
		} else {
			y++
		}
	}
	return false
}

總結:

要從排序的二元陣列(右邊的元素一律比左邊大，元素的正下方比上面的位置大，但並非整列的所有元素比上列大)中找出目標值，其做法只能從頭開始與鄰近的元素一一作比較並逐步靠進目標值，開始比較的位置如果從最右上角開始的話就可以用最簡單的方式及最快的路徑到達目標值，如果目標值比較大而需要往值大的地方移動時就只能往下移動，而如果目標值比較小而需要往值小的地方移動也就只能往左邊移動，最後當移動到超出二元陣列範圍外時便能確定此值不存在。

分享到