当前位置:聪少自媒体网 > 今日头条 > 正文

张博的博客

2020-10-05 今日头条 聪少自媒体

'''

链接:https://www.nowcoder.com/questionTerminal/f652bf7904bf4905804fa3bc347fdd2a

来源:牛客网

P为给定的二维平面整数点集。定义 P 中某点x,如果x满足 P 中任意点都不在 x 的右上方区域内(横纵坐标都大于x),则称其为“最大的”。求出所有“最大的”点的集合。(所有点的横坐标和纵坐标都不重复, 坐标轴范围在[0, 1e9) 内)

如下图:实心点为满足条件的点的集合。请实现代码找到集合 P 中的所有 ”最大“ 点的集合并输出。

'''

#下面来做题

#首先要有预处理思想,先对x坐标进行排序,python对tuple自动按照第一个坐标排序

number=input()

number=int(number)

#保存所有的点

listme=[]

for i in range(number):

a1=input()

a1=a1.split(' ')

a=int(a1[0])

b=int(a1[1])

listme.append((a,b))

listme=sorted(listme)

#为了效率先找到y max 和y min ,然后最后重新扫一次listme找到ymax和ymin中间的点.

#应该逆着找.

listme=listme[::-1]

b=[]

b.append(listme[0])

tmp=listme[0][1]

for i in range(1,len(listme)):

if listme[i][1]>tmp:

b.append(listme[i])

tmp=listme[i][1]

b=b[::-1]

for i in range(len(b)):

print(b[i][0],end=' ')

print(b[i][1])

'''

5

1 8

2 7

3 6

4 5

5 99

print("祝各位身体健康", end=' ')

print(23112,end=' ')

print(3243242)

'''

聪少爱学堂聪少
聪少爱学堂创始人,梅州市鹏鑫网络科技有限公司CEO,09年开始踏入互联网,10年互联网行业经验,资深自媒体人,自媒体优秀导师,咪挺微商团对营销引流顾问,业务包含:精准引流技术/代引流精准粉,专业小红书,知乎,微博代运营。
  • 38988文章总数
  • 1491134访问次数
  • 建站天数
  • 合作伙伴