未分類

Kth Smallest Element in a Sorted Matrix

BinarySearch, Go, Heap, LeetCode

Kth Smallest Element in a Sorted Matrix

Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

For Example:

1
2
3
4
5
6
7
8
matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,
return 13.

Note:

You may assume k is always valid, 1 ≤ k ≤ n^2.

提示 解題應用
BinarySearch BinarySearch

Default:

1
2
3
func kthSmallest(matrix [][]int, k int) int {
}

解答思路:

最初也是乾脆全數取出並由小至大做排序，再取第k個位置的值做回傳，不過發現討論區有人用二元搜尋似乎也是不錯的選擇，這裡的二分法跟一般的做法不太一樣，原本是取兩個邊界”位置”正中間index上的值來做為中間值進行比較，而這次則是取兩個邊界的”值”來取平均值做為中間值，之所以這麼做就是因為整個二元陣列的資料並非完全照順序排，也就是說每列的最後一個值並不一定比下一列的第一個小，唯一可以確定的就是最左上角與最右下角的值必定為最小與最大值，因此有了平均數之後接下來就只要與整個二元陣列的資料進行比較，如果比平均數小或相等就將計數器+1，最後計數器的統計與k比較大小，如果比k小平均數+1的值就放置開頭邊界，而如果相等或比k大則平均數放置結尾邊界，不斷重覆上述動作直到兩邊界值相等，其相等值就會是我們要找的結果，跑完整個測資比先前的做法稍為快了10ms。

程式碼解說:

如思路所述，一開始便將二元陣列最左上角與最右下角的值分別放置開頭邊界與結尾邊界，接著取平均數與接下來整個二元陣列的資料進行比較(記得每次比較前都要將計數器歸0)，如果比平均數小或相等就將計數器+1，比平均數大的話同列後頭的數字肯定也是如此，便跳開內層的迴圈繼續檢查下一列的數字，最後計數器的統計與k比較大小，如果比k小平均數+1的值就放置開頭邊界，而如果相等或比k大則平均數放置結尾邊界，不斷重覆上述動作直到兩邊界值相等，其相等值就會是我們要找的結果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
var mid int
var count int
front := matrix[0][0]
rear := matrix[len(matrix)-1][len(matrix)-1]
for front < rear {
	mid = (front + rear) / 2
	count = 0
	for i := 0; i < len(matrix); i++ {
		for j := 0; j < len(matrix); j++ {
			if matrix[i][j] <= mid {
				count++
			} else {
				break
			}
		}
	}
	if count < k {
		front = mid + 1
	} else {
		rear = mid
	}
}
return front

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func kthSmallest(matrix [][]int, k int) int {
	var mid int
	var count int
	front := matrix[0][0]
	rear := matrix[len(matrix)-1][len(matrix)-1]
	for front < rear {
		mid = (front + rear) / 2
		count = 0
		for i := 0; i < len(matrix); i++ {
			for j := 0; j < len(matrix); j++ {
				if matrix[i][j] <= mid {
					count++
				} else {
					break
				}
			}
		}
		if count < k {
			front = mid + 1
		} else {
			rear = mid
		}
	}
	return front
}

總結:

有一nxn的二元陣列，每橫排右邊的值必定比左邊大，每直列下面的值必定比右邊大，要找出整個二元陣列中第k小的值，其做法是用二元搜尋，不過這裡的二分法是取兩個邊界的”值”來取平均值做為中間值，因為整個二元陣列的資料並非完全由左上小至右下大排序，唯一可以確定的就是最左上角與最右下角的值必定為最小與最大值，因此有了平均數之後接下來就只要與整個二元陣列的資料進行比較，如果比平均數小或相等就將計數器+1，最後計數器的統計與k比較大小，如果比k小平均數+1的值就放置開頭邊界，而如果相等或比k大則平均數放置結尾邊界，不斷重覆上述動作直到兩邊界值相等，其相等值就會是我們要找的結果。

分享到