Python每日一题(15)

一、题目

题目描述

您需要写一种数据结构，来维护一些数（都是绝对值 $10^9$ 以内的数）的集合，最开始时集合是空的。其中需要提供以下操作，操作次数 $q$ 不超过 $10^4$：

1. 定义数 $x$ 的排名为集合中小于 $x$ 的数的个数 $+1$。查询数 $x$ 的排名。注意 $x$ 不一定在集合里。
2. 查询排名为 $x(x\ge 1)$ 的数。保证集合里至少有 $x$ 个数。
3. 求 $x$ 的前驱（前驱定义为小于 $x$，且最大的数）。若不存在则输出 $-2147483647$。
4. 求 $x$ 的后继（后继定义为大于 $x$，且最小的数）。若不存在则输出 $2147483647$。
5. 插入一个数 $x$，本题的数据保证插入前 $x$ 不在集合中。

保证执行 $1,3,4$ 操作时，集合中有至少一个元素。

输入格式

第一行是一个整数 $q$，表示操作次数。

接下来 $q$ 行，每行两个整数 $op,x$，分别表示操作序号以及操作的参数 $x$。

输出格式

输出有若干行。对于操作 $1,2,3,4$，输出一个整数，表示该操作的结果。

输入输出样例 #1

输入 #1

7
5 1
5 3
5 5
1 3
2 2
3 3
4 3

输出 #1

2
3
1
5

二、分析

  整体上打算封装成类，然后分别定义函数input()、_insert()、_one()、_two()、_three()、_four()分别解决对应问题。其中的12345分别对应函数one two three four _insert，操作数1234用英语不会写，所以直接用对应英语单词代替了。然后内部实现细节主要应用了二分查找方式，这里不做细致展开。整体上就看类的封装。

三、源代码

class SolveProblems:def __init__(self):self.nums = []  def input(self):q = int(input())for _ in range(q):op, x = map(int, input().split())if op == 1:print(self.one(x))elif op == 2:print(self.two(x))elif op == 3:print(self.three(x))elif op == 4:print(self.four(x))elif op == 5:self._insert(x)def _insert(self, x):left, right = 0, len(self.nums)while left < right:mid = (left + right) // 2if self.nums[mid] < x:left = mid + 1else:right = midself.nums.insert(left, x)def one(self, x):left, right = 0, len(self.nums)while left < right:mid = (left + right) // 2if self.nums[mid] < x:left = mid + 1else:right = midreturn left + 1def two(self, x):return self.nums[x-1]def three(self, x):left, right = 0, len(self.nums)while left < right:mid = (left + right) // 2if self.nums[mid] < x:left = mid + 1else:right = midif right == 0:return -2147483647return self.nums[right-1]def four(self, x):left, right = 0, len(self.nums)while left < right:mid = (left + right) // 2if self.nums[mid] <= x:left = mid + 1else:right = midif left == len(self.nums):return 2147483647return self.nums[left]if __name__ == "__main__":solver = SolveProblems()solver.input()

  写着写着把输出跟输入写到一起了，没注意，就不修改了。one two three four是类内部函数，理论上应该加上_。输出结构也没有问题。内部实现细节等之后说到查找的时候，再细致讲解。

四、deepseek

import bisectq = int(input())
nums = []for _ in range(q):op, x = map(int, input().split())if op == 1:# 查询x的排名：小于x的数的个数 +1rank = bisect.bisect_left(nums, x) + 1print(rank)elif op == 2:# 查询排名为x的数print(nums[x-1])elif op == 3:# 前驱：最大的小于x的数pos = bisect.bisect_left(nums, x)if pos == 0:print(-2147483647)else:print(nums[pos-1])elif op == 4:# 后继：最小的大于x的数pos = bisect.bisect_right(nums, x)if pos == len(nums):print(2147483647)else:print(nums[pos])elif op == 5:# 插入x，保证之前不存在bisect.insort(nums, x)

  这里deepseek用到了python的一个库，bisect，这里我之前没用过，也不是很熟悉。但是从内部实现来看，似乎十分方便。bisect模块来模拟部分操作，因为bisect提供的函数可以在O(log n)时间内完成插入和查找，但其他操作需要额外处理。
***维护有序列表：***我们可以使用一个列表来动态维护有序的元素集合。这样可以利用二分查找来高效地执行各种操作：
插入操作（5）：使用bisect.insort来保持列表有序。
查询排名（1）：使用bisect.bisect_left找到插入位置，该位置即为小于x的数的个数，排名则是该位置+1。
查询第k小的数（2）：直接访问有序列表中的第k-1个元素（因为列表是0-based的）。
前驱查询（3）：使用bisect.bisect_left找到x的插入位置，前驱是该位置前一个位置的元素，如果位置为0则不存在。
后继查询（4）：使用bisect.bisect_right找到x的插入位置，后继是该位置的元素，如果位置超出列表长度则不存在。