Joyce' Blog
0%

find-first-and-last-position-of-element-in-sorted-array

发表于

题目描述

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。你的算法时间复杂度必须是 O(log n) 级别。如果数组中不存在目标值，返回 [-1, -1]。

题解

左右加减找下标的想法比较简单，但时间复杂度是O(n). 整个数组都是target值，往两边延伸复杂度最差会变成O(n+logn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<int> searchRange(vector<int>& nums, int target) {
	int left = 0;
	int right = nums.size() - 1;
	int mid;
	int position = -1;
	while (left <= right)
	{
		mid = (left + right) / 2;
		if (nums[mid] == target)
		{
			position = mid;
			break;
		}
		else if (nums[mid] < target)left = mid + 1;
		else right = mid - 1;
	}
	if (position == -1)return{ -1,-1 };
	int begin = position, end = position;
	while (begin > 0 && nums[begin-1] == target)begin--;
	while (end<nums.size()-1 && nums[end+1] == target)end++;
	return{ begin,end };
}

原来是有库函数的啊！

lower_bound(): 指向首个不小于 value 的元素的迭代器，或若找不到这种元素则为 last
upper_bound(): 指向首个大于 value 的元素的迭代器，或若找不到这种元素则为 last

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
vector<int> searchRange1(vector<int>& nums, int target)
{
	auto begin = lower_bound(nums.begin(), nums.end(), target);
	auto end = upper_bound(nums.begin(), nums.end(), target);
	int t1 = -1, t2 = -1;
	if (begin != nums.end())
	{
		t1 = begin - nums.begin();
		if (nums[t1] != target)
		{
			return{ -1,-1 };
		}
	}
	t2 = end - nums.begin() - 1;
	if (t2 >= 0)
	{
		if (nums[t2] != target)
			return{ -1,-1 };
	}
	else
		t2 = t1;
	return{ t1,t2 };
}

题目描述

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

题解

1
2
3
4
5
int searchInsert(vector<int>& nums, int target) {
	auto left = lower_bound(nums.begin(), nums.end(), target);
	int res = left - nums.begin();
	return res;
}