今日头条笔试第一题解题思路
先按照y降序排序,然后循环遍历x坐标,当x为当前遍历坐标的x最大值时,即为所要的坐标,以x为键加入加入到TreeMap中,最后,遍历TreeMap输出坐标,时间负责度为nlgn+n。今天早上刚想出来的,没有实际测试,还请大神指正
所有符合要求点的情况一定是按照下图的梯度方式的,坐标为红点
代码如下,仅供参考
import java.util.*; /** * 先按照y降序排序,然后循环遍历x坐标,当x为当前遍历坐标的x最大值时,即为所要的坐标, * 以x为键加入加入到TreeMap中,最后,遍历TreeMap输出坐标,时间负责度为nlgn+n。 */ public class Main00 { public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int x =0; int y = 0; TreeMap<Integer,Integer> map = new TreeMap<>(); //定义TreeMap按照K降序排列 TreeMap<Integer,Integer> map01 = new TreeMap<>(new Comparator<Integer>() { @Override public int compare(Integer o1, Integer o2) { return o2-o1; } }); for(int i=0;i<n;i++){ x = sc.nextInt(); y = sc.nextInt(); map01.put(y,x); } //遍历map01,将x大于前面所以值的最大值所在的坐标加入map Iterator<Map.Entry<Integer, Integer>> it01 = map01.entrySet().iterator(); int max = -1; while (it01.hasNext()) { Map.Entry<Integer, Integer> entry = it01.next(); if(entry.getValue()>max){ max = entry.getValue(); map.put(entry.getValue(),entry.getKey());
} } //遍历输出 Iterator<Map.Entry<Integer, Integer>> it = map.entrySet().iterator(); while (it.hasNext()) { Map.Entry<Integer, Integer> entry = it.next(); System.out.println( entry.getKey() + " " + entry.getValue()); } } }