LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置

题目描述

✅ 34. 在排序数组中查找元素的第一个和最后一个位置

image-20230305132114938

思路分析

等于给定值的第一个元素和最后一个元素

image-20250507164433466

image-20250507170921878

参考代码



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



func searchRange(nums []int, target int) []int {
	// 查找第一个位置
	first := func() int {
		left, right := 0, len(nums)-1
		res := -1

		for left <= right {
			mid := left + (right-left)/2
			if nums[mid] > target {
				right = mid - 1
			} else if nums[mid] < target {
				left = mid + 1
			} else {
				res = mid
				right = mid - 1
			}
		}

		return res
	}

	// 查找最后一个位置
	last := func() int {
		left, right := 0, len(nums)-1
		res := -1

		for left <= right {
			mid := left + (right-left)/2
			if nums[mid] > target {
				right = mid - 1
			} else if nums[mid] < target {
				left = mid + 1
			} else {
				res = mid
				left = mid + 1
			}
		}

		return res
	}

	start := first()
	end := last()
	return []int{start, end}
}





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



func searchRange(nums []int, target int) []int {
	// 查找第一个位置
	first := func() int {
		left, right := 0, len(nums)-1
		for left <= right {
			mid := left + (right-left)/2
			if nums[mid] > target {
				right = mid - 1
			} else if nums[mid] < target {
				left = mid + 1
			} else {
				right = mid - 1
			}
		}
		if left < len(nums) && nums[left] == target {
			return left
		}
		return -1
	}

	// 查找最后一个位置
	last := func() int {
		left, right := 0, len(nums)-1
		for left <= right {
			mid := left + (right-left)/2
			if nums[mid] > target {
				right = mid - 1
			} else if nums[mid] < target {
				left = mid + 1
			} else {
				left = mid + 1
			}
		}
		if right >= 0 && nums[right] == target {
			return right
		}
		return -1
	}

	start := first()
	end := last()
	return []int{start, end}
}





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



func searchRange(nums []int, target int) []int {
	left := findLeft(nums, target)
	right := findRight(nums, target)
	return []int{left, right}
}

// 找左边界（第一个等于 target 的位置）
func findLeft(nums []int, target int) int {
	left, right := 0, len(nums)-1
	res := -1
	for left <= right {
		mid := left + (right-left)/2
		if nums[mid] < target {
			left = mid + 1
		} else if nums[mid] > target {
			right = mid - 1
		} else if nums[mid] == target {
			res = mid
			right = mid - 1
		}
	}
	return res
}

// 找右边界（最后一个等于 target 的位置）
func findRight(nums []int, target int) int {
	left, right := 0, len(nums)-1
	res := -1
	for left <= right {
		mid := left + (right-left)/2
		if nums[mid] > target {
			right = mid - 1
		} else if nums[mid] < target {
			left = mid + 1
		} else if nums[mid] == target {
			res = mid
			left = mid + 1
		}
	}
	return res
}
  • 时间复杂度：O (log n)，因为我们使用了二分查找。
  • 空间复杂度：O (1)，只使用了常数级别的额外空间。

➡️ 点击查看 Java 题解



1



write your code here

image-20250507170020032

本文作者:
本文链接: https://hgnulb.github.io/blog/2025/81925119
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！