class Solution { public: /** * 二分查找 * @param n int整型 数组长度 * @param v int整型 查找值 * @param a int整型vector 有序数组 * @return int整型 */ int upper_bound_(int n, int v, vector<int>& a) { // write code here if(a[n-1] < v) return n + 1; //数组中所有数字都比给定的小,不存在,返回数组长度+1 int left = 0; int right = n - 1; while(left < right){ int mid = left + (right - left) / 2; //这样写防止溢出 if(a[mid] >= v) right = mid; else left = mid + 1; } return left+1; //本题输出的位置是从1开始计算的,但是我们的区间是用的数组下标,所以最后要输出left+1(right+1); } };用python写
时间: 2024-02-14 14:35:53 浏览: 26
class Solution:
def upper_bound_(self, n: int, v: int, a: List[int]) -> int:
if a[n-1] < v:
return n + 1
left = 0
right = n - 1
while left < right:
mid = left + (right - left) // 2
if a[mid] >= v:
right = mid
else:
left = mid + 1
return left + 1
相关问题
给定一个节点数为n的无序单链表,对其按升序排序。生成c++代码,class Solution { public: /** * * @param head ListNode类 the head node * @return ListNode类 / ListNode sortInList(ListNode* head) { // write code here } };
可以使用归并排序来对无序单链表进行排序。具体实现步骤如下:
1. 如果链表为空或只有一个节点,则无需排序,直接返回头节点。
2. 使用快慢指针法将链表分成两个部分,即将链表从中间断开,分成左右两个部分。
3. 对左右两个部分分别进行递归排序。
4. 将左右两个部分合并成一个有序链表。
5. 返回合并后的链表头节点。
以下是对应的C++代码实现:
class Solution {
public:
ListNode* sortInList(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return head;
}
ListNode* slow = head;
ListNode* fast = head->next;
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
}
ListNode* right = sortInList(slow->next);
slow->next = nullptr;
ListNode* left = sortInList(head);
return merge(left, right);
}
private:
ListNode* merge(ListNode* left, ListNode* right) {
ListNode dummy(0);
ListNode* tail = &dummy;
while (left != nullptr && right != nullptr) {
if (left->val < right->val) {
tail->next = left;
left = left->next;
} else {
tail->next = right;
right = right->next;
}
tail = tail->next;
}
if (left != nullptr) {
tail->next = left;
} else {
tail->next = right;
}
return dummy.next;
}
};
/** * 添加 * * @param building * @return int */ int add(Building building);
这是一个BuildingService接口中的add方法的定义,用来向数据库添加建筑物信息。方法返回一个int类型的值,表示添加操作的结果,通常是1表示成功,0表示失败。该方法接收一个Building类型的参数,表示需要添加的建筑物对象。具体的实现可以根据不同的需求,在对应的BuildingService实现类中完成。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)