2018字节跳动测试开发第一批

第一题编程题

时间复杂度，空间复杂度要求：

时间限制：1秒
空间限制：32768K

问题描述：

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

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

2018字节跳动测试开发第一批
输入描述：

第一行输入点集的个数 N， 接下来 N 行，每行两个数字代表点的 X 轴和 Y 轴。
对于 50%的数据,  1 <= N <= 10000;
对于 100%的数据, 1 <= N <= 500000;

输出描述：

输出“最大的” 点集合， 按照 X 轴从小到大的方式输出，每行两个数字分别代表点的 X 轴和 Y轴。

输入示例：

输出示例：

4 6
7 5
9 0

思路：

上来就是干。写了个O(n^2)的算法，只过了20%的case。。
O(n^2)的思路：
	对于每一个点，遍历整个列表，看看谁的x比它大而且y也比它大。如果有，这个点就不是目标值。

O(nlogn的思路)
后来老感觉抓住了点什么东西，又感觉没抓住。想了想，可以先按照x排下序(nlogn)，从x的最大值开始遍历，
这样的话对于每个x来讲，只需要判断之前出现过的最大的y是不是比自己的y要大就可以了。不大就是
最大值。 耗时O(n)
应该还有更好的办法，因为这个办法只过了80%的case。

解决方案1(O(n^2)):

nums = int(input())
s = set()
# 读入数据
for i in range(nums):
    a,b = input().split()
    k = int(a),int(b)
    s.add(k)
res = set()
for i in s:
    flag = True
    for j in s:
        if j[0]>i[0] and j[1]>i[1]:
            flag = False
            break
    if flag:
        res.add(i)
res = list(res)
res.sort(key=lambda x:x[0])

for i in res:
    print(i[0],i[1])

解决方案2：

nums = int(input())
l = []
for i in range(nums):
    x,y = input().split()
    k = int(x),int(y)
    l.append(k)

l.sort(key=lambda m:m[0])
res = []
max_y = None
for i in range(nums-1,-1,-1):
    if i == nums-1:
        res.append(l[i])
        max_y = l[i][1]
        continue
    if l[i][1] >= max_y:
        res.append(l[i])
        max_y = l[i][1]
    else:
        continue
res = res[::-1]
for i in res:
    print(i[0],i[1])

2018字节跳动测试开发第一批

第一题 编程题

相关推荐

第一题编程题