Leaky Cauldron
0%

Go 自定义类型排序

Posted on Edited on

题目(LeetCode #56)

给出一个区间的集合，请合并所有重叠的区间。

示例 1:

输入: intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
输出: [[1, 6], [8, 10], [15, 18]]
解释: 区间 [1, 3] 和 [2, 6] 重叠, 将它们合并为 [1, 6].

示例 2:

输入: intervals = [[1, 4], [4, 5]]
输出: [[1, 5]]
解释: 区间 [1, 4] 和 [4, 5] 可被视为重叠区间。

提示： intervals[i][0] <= intervals[i][1]

题解

  • 先按照每个区间的左端点进行排序，保证可以合并的区间是连续的。
  • 遍历区间数组，判断结果集中最后一个区间的右端点与当前数组的左端点的关系：
    • 若 curInterval[0] < mergedList[-1][1] ，则区间无重合，直接将当前区间放入结果集即可
    • 若 curInterval[0] >= mergedList[-1][1] ，则区间重合，需更新结果集中最后一个区间的右端点为 max(curInterval[1], mergerdList[-1][1])

快速排序

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
func merge(intervals [][]int) [][]int {
	if intervals == nil || len(intervals) <= 1 {
		return intervals
	}
	quickSort(intervals, 0, len(intervals)-1)

	var result [][]int
	result = append(result, intervals[0])
	for _, interval := range intervals[1:] {
		lastInterval := result[len(result)-1]
		if lastInterval[1] < interval[0] {
			result = append(result, interval)
		} else {
			lastInterval[1] = max(lastInterval[1], interval[1])
		}
	}

	return result
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func quickSort(nums [][]int, L, R int) {
	if L < R {
		pIndex := partition(nums, L, R)
		quickSort(nums, L, pIndex-1)
		quickSort(nums, pIndex+1, R)
	}
}

func partition(nums [][]int, L, R int) int {
	P := nums[L]
	for L != R {
		for L < R && nums[R][0] >= P[0] {
			R--
		}
		nums[L] = nums[R]
		for L < R && nums[L][0] <= P[0] {
			L++
		}
		nums[R] = nums[L]
	}
	nums[L] = P

	return L
}

Go 内置排序

调用 sort 包对自定义类型进行排序时，需实现其中的 Less() 、Len() 、Swap() 三个方法。

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import "sort"

func merge(intervals [][]int) [][]int {
	if intervals == nil || len(intervals) <= 1 {
		return intervals
	}
	sort.Sort(intss(intervals))

	var result [][]int
	result = append(result, intervals[0])
	for _, interval := range intervals[1:] {
		lastInterval := result[len(result)-1]
		if lastInterval[1] < interval[0] {
			result = append(result, interval)
		} else {
			lastInterval[1] = max(lastInterval[1], interval[1])
		}
	}

	return result
}

type intss [][]int

func (s intss) Swap(i, j int) {
	s[i], s[j] = s[j], s[i]
}

func (s intss) Less(i, j int) bool {
	return s[i][0] < s[j][0]
}

func (s intss) Len() int {
	return len(s)
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}