IT评测·应用市场-qidao123.com技术社区

标题: Leetcode 34 Find First and Last Position of Element in Sorted Array [打印本页]

---

作者: 海哥    时间: 2024-11-11 17:57
标题: Leetcode 34 Find First and Last Position of Element in Sorted Array
题意：找到非严格递增的数组中和target相等的左右边界
https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/description/
解答： 经典二分，找左右边界，要查看l是否满足题意

1. class Solution {
2. public:
3.     vector<int> searchRange(vector<int>& a, int t) {
4.         if (a.empty()) return {-1, -1};
5.         int first = findFirst(a, t);
6.         int second = findLast(a , t);
7.         return {first, second};
8.     }
9.     int findFirst(vector<int>& a, int t) {
10.         int l = 0;
11.         int r = a.size() - 1;
12.         while (l < r) {
13.             int mid = l + (r - l) / 2;
14.             if(a[mid] >= t) {
15.                 r = mid;
16.             } else {
17.                  l = mid + 1;
18.             }
19.         }
20.         return a[l] == t ? l : -1;
21.     }
23.     int findLast(vector<int>& a, int t) {
24.         int l = 0;
25.         int r = a.size() - 1;
26.         while (l < r) {
27.             int mid = l + (r - l) + 1 / 2;
28.             if(a[mid] <= t) {
29.                 l = mid;
30.             } else {
31.                 r = mid - 1;
32.             }
33.         }
34.         return a[l] == t ? l : -1;
35.     }
37. };

复制代码

算法复杂度：O(2logN), N是数组长度，空间复杂度O（1）

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 IT评测·应用市场-qidao123.com技术社区 (https://dis.qidao123.com/)

Powered by Discuz! X3.4