時間限制：C/C++ 1秒，其他語言2秒

空間限制：C/C++ 32M，其他語言64M

P為給定的二維平面整數(shù)點集。定義 P 中某點x，如果x滿足 P 中任意點都不在 x 的右上方區(qū)域內(nèi)（橫縱坐標(biāo)都大于x），則稱其為“最大的”。求出所有“最大的”點的集合。（所有點的橫坐標(biāo)和縱坐標(biāo)都不重復(fù), 坐標(biāo)軸范圍在[0, 1e9) 內(nèi)）

如下圖：實心點為滿足條件的點的集合。請實現(xiàn)代碼找到集合 P 中的所有 ”最大“ 點的集合并輸出。

輸入描述:

第一行輸入點集的個數(shù) N， 接下來 N 行，每行兩個數(shù)字代表點的 X 軸和 Y 軸。

對于 50%的數(shù)據(jù), 1 <= N <= 10000;

對于 100%的數(shù)據(jù), 1 <= N <= 500000;

輸出描述:

輸出“最大的” 點集合， 按照 X 軸從小到大的方式輸出，每行兩個數(shù)字分別代表點的 X 軸和 Y軸。

輸入例子1:

5 1 2 5 3 4 6 7 5 9 0

輸出例子1:

4 6 7 5 9 0

Ideas

首先可以發(fā)現(xiàn)所有 ”最大“ 點都在右上方圍了一圈，因此可以利用這個特征來做題。

先把所有的點都按照y值排序，那么y值最大的那個點肯定是右下角的“最大”點，記為p0，然后按照y值依次往前遍歷，遍歷到p點的x值是大于前一個p點的x值，說明找到了一個“最大”點。

Code

Python

Python的代碼只能過 9/10 組用例，最后一個內(nèi)存超限，求大佬指點，怎么能過最后一組數(shù)據(jù)，我感覺可以優(yōu)化的地方在處理輸入的位置，暫時沒想到更好的優(yōu)化方案。

if __name__ == '__main__':point_list = []n = int(input())for _ in range(n):point_list.append(tuple(map(int, input().split())))max_x = 0point_list.sort(key=lambda x: x[1])for i in range(n - 1, -1, -1):if point_list[i][0] > max_x:print(f"{point_list[i][0]} {point_list[i][1]}")max_x = point_list[i][0] 與50位技術(shù)專家面對面20年技術(shù)見證，附贈技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的字节跳动2018校招算法方向（第一批） —— 1-最外层点的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。