ZJ11（字节2018）字节跳动2018校招测试开发方向（第一批）

题目描述：

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

输入描述：

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

输出描述：

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

示例1：

输入

5
1 2
5 3
4 6
7 5
9 0

输出

4 6
7 5
9 0

问题分析：

思路一：（C++实现）按照y值从大到小排序，然后扫描，保存当前最大的x，如果该点比x大，那么该点满足条件。注意要使用scanf,printf,使用cin,cout会超时。
思路二：（java实现），同样是使用“预排序”处理，但是C++可以通过，Java却不可以，说明该方法并不是出题者需要的，出题者需要更加快的。同时也说明，使用暴力法是肯定会超时的。
于是只能考虑其他的方法。

暴力搜索法
先取一点，然后和其他所有点比较，看看是否有点在其右上方，没有则证明该点是“最大点”。重复检测所有的点。显而易见，算法的复杂度为O(n2)。
变治法(预排序)
由“最大点”的性质可知，对于每一个“最大点”，若存在其他点的y值大于该点y值，那么其他点x值必然小于该点的x值。
换言之，当某一点确定它的x值高于所有y值大于它的点的x值，那么该点就是“最大点” 。网上给出的答案基本上都是基于这个思路。
对于y有序的点集，只需要O(n)即可输出“最大点”点集。一般基于比较的排序算法时间复杂度O(nlogn)。那么，显而易见，算法整体复杂度为O(nlogn)。
减治法+变治法(过滤+预排序)
过滤很简单，就是在集合中找出一个比较好的点，然后过滤掉其左下角的所有点。然后再采用方法2对过滤后的点集求解。
那么这个集合中比较好的点，怎么找，或者说哪个点是比较好的点。显而易见，越靠近点集右上角的点，左下角的面积就越大，越可以过滤更多的点，故越好。
根据数学知识，两个数的和一定，那么两数差越小，乘积越大。简单设计，该点x和y的和减去x和y差的绝对值越大，该点越好。

参考代码：

思路一实现：

//按照y值从大到小排序，然后扫描，保存当前最大的x，如果该点比x大，那么该点满足条件
//注意要使用scanf,printf,使用cin,cout会超时
#include <iostream>
#include <algorithm>
using namespace std;
struct point
{
    int x,y;
};
point p[500001];
bool cmp(point p1, point p2)
{
    return p1.y>p2.y;
}
int main(void)
{
    int n;
    scanf("%d", &n);
    for (int i=0; i<n; i++)
    {
        scanf("%d%d",&p[i].x,&p[i].y);
    }
    sort(p,p+n,cmp);
    int x_max = -1;
    for (int i=0; i<n; i++)
    {
        if (x_max<p[i].x)
        {
            x_max = p[i].x;
            printf("%d %d\n", p[i].x, p[i].y);
        }
    }
    return 0;
}

思路二实现：（使用java，同样使用预排序，容易超时）

import java.util.*;
public class Main {
    public static void main(String[] args)
    {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        ArrayList<Point> points = new ArrayList<>();
        ArrayList<Point> resPoints = new ArrayList<>();
        for (int i=0; i<n; i++)
        {
            points.add(new Point(input.nextInt(),input.nextInt()));  
        }
        Collections.sort(points, new MyComparator());
        int max = -1;
        for (int i=0; i<n; i++)
        {
            if (points.get(i).x > max)
            {
                max = points.get(i).x;
                System.out.println(points.get(i).x + " " + points.get(i).y);
            }
        }
    }
}

class Point
{
    int x;
    int y;
    Point(int xx, int yy)
    {
        this.x = xx;
        this.y = yy;
    }
}
class MyComparator implements Comparator<Point>
{
    public int compare(Point p1, Point p2)
    {
        return p2.y-p1.y;  //降序
    }
}

ZJ11（字节2018）字节跳动2018校招测试开发方向（第一批）

题目描述：

输入描述：

输出描述：

示例1：

问题分析：

相关知识：

参考代码：