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

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

题目表述

题目链接

C++代码

#pragma once
#include <iostream>
#include<vector>

using namespace std;


//打印容器
void show_vector(vector<int>& v)
{
	vector<int>::iterator it;
	for (it = v.begin(); it != v.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}



class Solution {
public:
	vector<int> searchRange(vector<int>& nums, int target) 
	{
		//创建容器用于存放元素索引
		vector<int>res;
		//创建容器-不符合条件时的输出
		vector<int>no_res(2,-1);
		//打印不符合要求的输出
		cout << "不符合要求的输出：";
		show_vector(no_res);

		int n = nums.size();
		for (int i = 0; i < n; i++)
		{
			//关键字等于目标值时将索引添加到res容器
			if (nums[i] == target)
			{
				res.push_back(i);
				continue;
			}
		}

		//添加元素后，容器为空，输出不符合条件的容器
		//测试容器中没有目标值的情况
		if (res.empty())
		{
			return no_res;
		}
		//添加元素后若容器不为空
		else
		{
			//创建结果容器，存放上述容器的第一个元素和最后一个元素
			//1.测试容器中只有一个目标值
			//2.测试容器中有多个个目标值
			vector<int>result_v;
			result_v.push_back(res.front());
			result_v.push_back(res.back());
			return result_v;
		}

	}
};





int main()
{
	
	vector<int>v;
	v.push_back(5);
	v.push_back(7);
	v.push_back(7);
	v.push_back(8);
	v.push_back(8);
	v.push_back(10);

	cout << "测试容器中的元素：";
	show_vector(v);


	Solution S;
	vector<int> result = S.searchRange(v, 8);

	cout << "得到的结果：" ;
	show_vector(result);

	system("pause");
	return 0;
}

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

运行结果

使用二分法

//使用二分法

class Solution {
public:
	//获取左边界
	int getLeftBorder(vector<int>& nums, int target)
	{
		//左右边界初始值
		int left = 0;
		int right = nums.size() - 1;
		//边界结果
		int ans = nums.size();

		while (left <= right) 
		{
			int middle = (left + right) / 2;
			if (nums[middle] >= target)
			{
				right = middle - 1;
				ans = middle;
			}
			else {
				left = middle + 1;
			}
		}
		return ans;
	}

	//获取右边界
	int getRightBorder(vector<int>& nums, int target) 
	{
		int left = 0;
		int right = nums.size() - 1;
		//边界结果
		int ans = nums.size();

		while (left <= right) {
			int mid = (left + right) / 2;
			if (nums[mid] > target ) {
				right = mid - 1;
				ans = mid;
			}
			else {
				left = mid + 1;
			}
		}
		return ans;
	}

	vector<int> searchRange(vector<int>& nums, int target) {
		int leftIdx =getLeftBorder(nums, target);
		int rightIdx = getRightBorder(nums, target) - 1;
		if (leftIdx <= rightIdx && rightIdx < nums.size() && nums[leftIdx] == target && nums[rightIdx] == target) {
			return vector<int>{leftIdx, rightIdx};
		}
		return vector<int>{-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
52
53
54
55
56
57
58
59