今日头条后台笔试第一道编程题解法

当时没做完，后来花了一点时间把它做完，应该是ac了，但是时间复杂度可能有点高。

题目大概是这样的：假设有一点x，其右上区域没有任何点，输出符合条件的点x。

思路是这样的：

1.先按照x轴的值对坐标点进行排序，最后一个点无论如何都满足条件。

2.再依次比较y轴的值，由于x值已经排好序（由小到大），y值只要遇到后面有比它大的，该点就不符合条件，继续循环判断下一个点是否符合条件。如果某一个点，其y值大于后面所有点的y值，该点符合条件，输出（注意是大于其后的所有的点的y值，前面有点的y值大于它，它仍旧符合条件，因为前面的点的x值是小于它的）。
代码如下：

import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner sc1 = new Scanner(System.in);
        int n = sc1.nextInt();
        int[][] intArray = new int[n][2];
        String str1 = null;
        Scanner sc2 = new Scanner(System.in);
        for(int i = 0; i < n; i++) {
             str1 = sc2.nextLine();
             String[] strArray = str1.split(" ");
             intArray[i][0] = Integer.parseInt(strArray[0]);
             intArray[i][1] = Integer.parseInt(strArray[1]);
        }
        //按x值，由小到大进行排序
        for(int i = 0; i < n - 1; i++) {
            for(int j = 0; j < n - i - 1; j++) {
                if(intArray[j][0] > intArray[j+1][0]) {
                    //将x轴值进行交换
                    int temp1 = intArray[j][0];
                    intArray[j][0] = intArray[j+1][0];
                    intArray[j+1][0] = temp1;
                    //y轴值必须跟着x走，作相同交换
                    int temp2 = intArray[j][1];
                    intArray[j][1] = intArray[j+1][1];
                    intArray[j+1][1] = temp2;
                }
            }
        }
        //对y值进行比较，由于x已经从小到大排序，只要后面数组的y值有更大的，该数组不满足条件
        int x ;
        for(int i = 0; i < n; i++){
            for(x = i + 1; x < n; x++){
                if(intArray[i][1] < intArray[x][1]) {

                    break;
                }
            }
            if(x == n || i == n) {
                System.out.print(intArray[i][0]);
                System.out.print(" ");
                System.out.print(intArray[i][1]);
                System.out.println();
            }
        }

    }
}