问题遇到的现象和发生背景
题目要求:
输入
5(输入的个数)
1 10 (1-10)
7 9
3 8
4 7 (4-7)
5 5 (5:5 只有5)
输出
1 1 (1、计算1出现的次数)
2 1(2、2出现的次数,为1)
3 2(3、3出现的次数,为2)
4 3
5 4
6 3
7 3
8 3
9 2
10 1
问题相关代码,请勿粘贴截图
a=int(input())
c = [[],[]]
for i in range(a):
b = [int(n) for n in input().split()]
c[0].append(b[0])
c[1].append(b[1])
for i in range(min(c[0]),max(c[1])+1):
m = len([n for n in c[0] if n<=i])
n = len([n for n in c[1] if n<i])
if m-n>0:
print(i,m-n)
运行结果及报错内容
此代码可以实现功能,但是时间复杂度大,需要优化
我的解答思路和尝试过的方法
PS:
教授上课讲的方法,仅供参考
假如需要查找6出现的个数
因为在[1 10]这个数组里
(我是数轴)—[1—6—10]—→√
在[7 9]这个数组里
(我是数轴)—6—[7—8—9]—→X
因此[a,b]如果满足
(我是数轴)—[a—6—b]—→√
(我是数轴)—6—[a—b]—→X
(我是数轴)—[a—b]—6—→X
现在将示例中5个数组
[1 10]
[7 9]
[3 8]
[4 7]
[5 5]
写成2个数组
A=[1 7 3 4 5] 左列
B=[10 9 8 7 5] 右列
找到A里≤6的数有4个(可能有6的数组数量)
B里<6的数有1个(在可能有6的数量里,没有6的数组数量)
所以6的出现的次数为4-1=3个