未分類

Find K Pairs with Smallest Sums

Go, Heap, LeetCode

Find K Pairs with Smallest Sums

You are given two integer arrays nums1 and nums2 sorted in ascending order and an integer k.

Define a pair (u,v) which consists of one element from the first array and one element from the second array.

Find the k pairs (u1,v1),(u2,v2) …(uk,vk) with the smallest sums.

Example 1:

1
2
3
4
5
6
Given nums1 = [1,7,11], nums2 = [2,4,6],  k = 3
Return: [1,2],[1,4],[1,6]
The first 3 pairs are returned from the sequence:
[1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]

Example 2:

1
2
3
4
5
6
Given nums1 = [1,1,2], nums2 = [1,2,3],  k = 2
Return: [1,1],[1,1]
The first 2 pairs are returned from the sequence:
[1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]

Example 3:

1
2
3
4
5
6
Given nums1 = [1,2], nums2 = [3],  k = 3 
Return: [1,3],[2,3]
All possible pairs are returned from the sequence:
[1,3],[2,3]

Default:

1
2
3
func kSmallestPairs(nums1 []int, nums2 []int, k int) [][]int {
}

解答思路:

看到題目很自然的就用巢狀迴圈列出所有數對的組合，並自行定義排序規則將上述組合做排序(數對總合比大小)，最後只要回傳前k個小的數對即可，不過題目給的數據已經有排序過了，所以相信可以再優化至更佳的結果，目前暫時先做保留。

程式碼解說:

這部分為自行定義的排序規則，最主要是以數對的總合來比大小，其中Len(),Swap(),Less()三個function前面兩個與一般排序規則並無差別，而複寫的便是Less()的比較，取出數對中的兩個值做加總才與另一對總合做比較

1
2
3
4
type sortPair [][]int
func (p sortPair) Len() int           { return len(p) }
func (p sortPair) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }
func (p sortPair) Less(i, j int) bool { return p[i][0]+p[i][1] < p[j][0]+p[j][1] }

有了自訂的排序規則之後，再來就只要用巢狀迴圈列出所有數對的組合，將其做排序之後便能回傳前k個小的數對，不過如果是整個數對的組合數小於等於k就只要回傳整個排序的組合即可

1
2
3
4
5
6
7
8
9
10
11
12
13
func kSmallestPairs(nums1 []int, nums2 []int, k int) [][]int {
	var result [][]int
	for _, n1 := range nums1 {
		for _, n2 := range nums2 {
			result = append(result, []int{n1, n2})
		}
	}
	sort.Sort(sortPair(result))
	if len(result) <= k {
		return result
	}
	return result[:k]
}

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
type sortPair [][]int
func (p sortPair) Len() int           { return len(p) }
func (p sortPair) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }
func (p sortPair) Less(i, j int) bool { return p[i][0]+p[i][1] < p[j][0]+p[j][1] }
func kSmallestPairs(nums1 []int, nums2 []int, k int) [][]int {
	var result [][]int
	for _, n1 := range nums1 {
		for _, n2 := range nums2 {
			result = append(result, []int{n1, n2})
		}
	}
	sort.Sort(sortPair(result))
	if len(result) <= k {
		return result
	}
	return result[:k]
}

總結:

給兩個已排序陣列要找出最小的k個總合數對(兩陣列各別取一個值作為數對)，最直覺的做法是利用巢狀迴圈列出所有數對的組合，並自行定義排序規則將上述組合做排序(數對總合比大小)，最後只要回傳前k個小的數對即可。

分享到