首页 > 试题广场 >

输出点集合

[编程题]输出点集合

热度指数：19313 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

输入

输出

4 6
7 5
9 0

算法知识视频讲解

Java

SharkeyBoy

提交结果：答案正确运行时间：1011ms 占用内存：63148KB 使用语言：Java 用例通过率：100.00%

这题Java需要桶排序+快速读入输出才能过

Arrays.sort 快排过不了。可能极限情况了吧

import java.util.*;
import java.io.*;

public class Main{
    public static void main(String[] args) throws Exception{
        
        // 快速输入输出
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        in.nextToken();
        int n = (int)in.nval;
        int[][] pts = new int[n][2];
        for(int i = 0;i < n;i ++){
            in.nextToken();
            pts[i][0] = (int)in.nval;
            in.nextToken();
            pts[i][1] = (int)in.nval;
        }
        sort(pts);
        List<Integer> ans = new ArrayList<>(); 
        ans.add(pts.length - 1);
        int maxs = pts[pts.length-1][1];
        for(int i = pts.length - 2;i >= 0;i --){
            if(pts[i][1] >= maxs){
                ans.add(i);
            }
            maxs = Math.max(maxs, pts[i][1]);
        }
        for(int i = ans.size() - 1;i >= 0;i --){
            out.println(pts[ans.get(i)][0] + " " + pts[ans.get(i)][1]);
        }
        out.flush();
    }   
    
    // 桶排序
    public static void sort(int[][] pts){
        int n = pts.length;
        int[] count = new int[10];
        int tp = 1;
        int[][] dp = new int[n][2];
        for(int i = 0;i < 10;i ++){
            for(int j = 0;j < 10;j ++){
                count[j] = 0;
            }
            for(int j = 0;j < n;j ++){
                int y = pts[j][0];
                count[y/tp%10] ++;
            }
            for(int j = 1;j < 10;j ++){
                count[j] += count[j-1];
            }
            for(int j = n - 1;j >= 0;j --){
                int pos = pts[j][0] / tp % 10;
                count[pos] --;
                dp[count[pos]][0] = pts[j][0];
                dp[count[pos]][1] = pts[j][1];
            }
            tp *= 10;
            for(int j = 0;j < n;j ++){
                pts[j][0] = dp[j][0];
                pts[j][1] = dp[j][1];
            }
        }
    }
}

发表于 2022-04-01 17:41:38 回复(0)

Java

牛客295778374号

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

/**
 * T18 
 * 和C++一样的逻辑，时间复杂度为N，竟然运行不通过，赤裸裸的歧视啊
 */
public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        List<Point> list = new ArrayList<>(500002);
        for (int i = 0; i < n; i++) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            list.add(new Point(x, y));
        }
        reslove1(list);
    }

    public static void reslove1(List<Point> list) {
        list.sort(new Comparator<Point>() {
            @Override
            public int compare(Point o1, Point o2) {
                int i = o1.x - o2.x;
                if (i == 0) {
                    i = o1.y - o2.y;
                }
                return i;
            }
        });
        List<Point> result = new ArrayList<>(500002);
        int maxy = -1;
        for (int i = list.size(); i > 0; i--) {
            Point p1 = list.get(i - 1);
            if (p1.y > maxy) {
                result.add(p1);
                maxy = p1.y;
            }
        }

        for (int i = result.size(); i > 0; i--) {
            Point t = result.get(i - 1);
            System.out.println(t.x + " " + t.y);
        }
    }


    static class Point {
        int x;
        int y;
        //默认为0，当不为0时，标识已经处理过
        int z;

        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

发表于 2021-09-03 17:13:11 回复(0)

Java

struggle666

快排+动态规划 Java

时间复杂度为O(nlogn) 只通过60%

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
public class Main{
  public static void main(String[] args) {
      Scanner scan = new Scanner(System.in);
      int n = Integer.parseInt(scan.nextLine());
      int[][] arr = new int[n][2];
      for (int i = 0; i < n; i++) {
          String[] line = scan.nextLine().split(" ");
          arr[i][0] = Integer.parseInt(line[0]);
          arr[i][1] = Integer.parseInt(line[1]);
      }

      // 按x的坐标从小到大排序
      Arrays.sort(arr, (o1, o2) -> o1[0] - o2[0]); 

      ArrayList<int[]> list = new ArrayList<>();
      // 使用动态规划从后往前
      int last_max = -1; // 记录当前下标后面的最大值
      for (int i = n - 1; i >= 0; i--) {
          // 如果后面的y值没有大于当前y值的就添加进去
          if (arr[i][1] > last_max) list.add(0, arr[i]); 
          last_max = Math.max(last_max, arr[i][1]); // 更新最大值
      }

      for (int[] temp : list) {
          System.out.println(temp[0] + " " + temp[1]);
      }
  }
}

发表于 2020-06-20 17:06:31 回复(0)

Java

大疯疯

/*
说算法的复杂度过大，只通过50%，哪位大佬帮忙看看啊。救救孩子！
筛选用的遍历
排序用的快速排序
*/
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int [][] arr = new int[n][2];
        for (int i = 0; i < n; i++) {
            arr[i][0] = scanner.nextInt();
            arr[i][1] = scanner.nextInt();
        }
        List<int[]> answer = new ArrayList<>();
        for (int i = 0; i < n ; i++) {
            boolean flag = true;
            int right = n-1;
            int left = 0;
            while(left<right){
                if ((left!=i) &&(arr[left][0]>arr[i][0]&&arr[left][1]>arr[i][1])){
                    flag = false;
                    break;
                }else if ((right!=i)&&(arr[right][0]>arr[i][0]&&arr[right][1]>arr[i][1])){
                    flag = false;
                    break;

                }
                left++;
                right--;
            }
            if (flag){
                answer.add(arr[i]);
            }
        }

        int size  = answer.size()/2;
        int[][] result = answer.toArray(new int[size][]);
        //结果集排序
        quickSort(result,0,result.length-1);

       //输出
        for (int i = 0; i < result.length; i++) {
            System.out.println(result[i][0]+" "+result[i][1]);
        }
    }

    //快速排序
    public static void  quickSort(int[][] arr,int low,int high){
        if (low>=high){
            return ;
        }
        int left = low;
        int right = high;
        int[] key = arr[low];
        while (left<right){
            while (arr[right][0]>=key[0] && left<right){
                right--;
            }
            while (arr[left][0]<=key[0] && left<right){
                left++;
            }
            if (left<right){
                int[] temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
            }
        }
        arr[low] = arr[left];
        arr[left] = key;

        quickSort(arr,low,left-1);
        quickSort(arr,left+1,high);
    }
}

编辑于 2020-05-01 10:27:18 回复(0)

Java

。201804111737858

/*****90 %***/

//java是不是不能100%啊，换了好几种方式了

import java.io.*;
import java.util.*;

/**
* @ClassName maxClass2Arraysort
* @Description TODO
* @Author Administrator
* @Data 20:57
* @Version 1.0
*/
public class Main {

public static void main(String[] args) throws IOException {

// BufferedReader in =new BufferedReader(new InputStreamReader(System.in));

InputReader inputReader = new InputReader(System.in);

PrintWriter out = new PrintWriter(System.out);

int N=Integer.parseInt(inputReader.next()); //int型输入
// int N = sc.nextInt();
int n= 0;
long [][]point = new long[N][2];
while(n<N){
// String absu[] = inputReader.next().split(" ");
point[n][0] = Long.parseLong(inputReader.next());
point[n][1] = Long.parseLong(inputReader.next());
n++;
}

sortArraylistLong(point);

long tmpMaxX = 0;
for(int t = 0;t < point.length; t++){
// System.out.println(pointX[t]+" "+pointY[t]);
if( t ==0 && point[t][1]>point[t+1][1] ){ //保证y最大

// arrayList.add(point[t]);
out.println(point[t][0]+" "+ point[t][1]);
tmpMaxX = point[t][0];
}else{
if(point[t][0] > tmpMaxX){
out.println(point[t][0]+" "+ point[t][1]);
tmpMaxX = point[t][0];
}
}

}
out.flush();

// for(int pps = arrayList.size()-1;pps >=0; pps--){
// System.out.printf("%s %s%n", arrayList.get(pps)[0], arrayList.get(pps)[1]);
// }

}

public static void sortArraylistLong(long[][] nums){

// int[][] nums = new int[][]{{1,3},{1,2},{4,5},{3,7}};
Arrays.sort(nums, new Comparator<long[]>() {
@Override
public int compare(long[] a, long[] b){
if(a[1]==b[1]){
return a[0]>b[0]?1:-1; // 1维一样，用2维排序
}else {
return a[1]>b[1]?-1:1;
}
}
});

//排序完成

}
}

class InputReader {

public BufferedReader reader;
public StringTokenizer tokenizer;

public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream), 32768);
tokenizer = null;
}

public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}

public int nextInt() {
return Integer.parseInt(next());
}

}

class sort{
public static void main(String[] args) {
int [] a = new int[]{1 , 8,9,6,1,4,5,2,3,5,4,8,5,5,2,5,5};
Arrays.sort(a);
for(int i = 0 ; i < a.length;i++){

System.out.println(a[i]);
}
long aa =1000000007;
System.out.println(aa*1000);

InputReader inputReader = new InputReader(System.in);
System.out.println(inputReader.next());

}
}

发表于 2020-03-20 00:17:05 回复(0)

Java

1+½+¼+⅛+...

import java.util.Scanner;
//只能通过70%,求大佬帮忙看看 
public class Main{
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int N = input.nextInt();
        int[][] p = new int[N][2];
        for(int i = 0; i < N; i++) {
            p[i][0] = input.nextInt();
            p[i][1] = input.nextInt();
        }
        input.close();
        Solution(N, p);
    }
    public static void Solution(int N, int[][] p){
       QuickSort(p, 0, N-1);
       int[] ymax = new int[N];
       ymax[N-1] = p[N-1][1];
       for(int i = N-2; i >= 0; i--) {
           ymax[i] = (p[i][1] > ymax[i+1]) ? p[i][1] : ymax[i+1];
       }
       for(int i = 0; i < N; i++) {
           if(p[i][1] == ymax[i]) {
               System.out.println(p[i][0]+" "+p[i][1]);
           }
       }
    }
     
    public static void QuickSort(int[][] p, int start, int end) {
        int i = start;
        int j = end;
        int k = p[start][0];
        int[] t;
        while(i < j) {
            t = p[i];
            while(i < j && p[j][0] >= k) {
                j --;
            }
            p[i] = p[j];
            p[j] = t;                  
            while(i < j && p[i][0] <= k) {
                i ++;
            }
            p[j] = p[i];
            p[i] = t;
        }
        if(i - 1 > start) QuickSort(p, start, i-1);
        if(i + 1 < end) QuickSort(p, i+1, end);
    }
}

编辑于 2019-09-12 12:56:46 回复(2)

Java

互联网反卷卫士

您的程序未能在规定时间内运行结束，请检查是否循环有错或算法复杂度过大。
case通过率为70.00%

import java.util.Scanner;
import java.util.Arrays;
import java.util.Comparator;

public class Main {

public static void sort(int[][] ob) {
Arrays.sort(ob, new Comparator<Object>() {
public int compare(Object o1, Object o2) {
int[] one = (int[]) o1;
int[] two = (int[]) o2;
for (int i = 1; i >=0; i--) {
if (one[i] > two[i]) {
return 1;
} else if (one[i] < two[i]) {
return -1;
} else {
continue; //如果按一条件比较结果相等，就使用第二个条件进行比较。
}
}
return 0;
}
});
}

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[][] point=new int[n][2];
for(int i=0; i<n; i++){
point[i][0]= in.nextInt();
point[i][1]= in.nextInt();
}
sort(point);
System.out.println(point[n-1][0]+" "+point[n-1][1]);
int maxX=point[n-1][0];
for(int j = n-2; j >=0; j--)
{
if(point[j][0] > maxX)
{
maxX=point[j][0];
System.out.println(point[j][0]+" "+point[j][1]);
}
}
}
}

编辑于 2019-03-15 19:24:32 回复(1)

Java

Windy心梦无痕#

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

class Port{     int x;     int y;
}

class cmp implements Comparator<Port>{     @Override     public int compare(Port o1, Port o2) {         if(o1.y < o2.y) {             return 1;         }else{             return -1;         }     }
}

public class Main{     public static void main(String[] args) {         @SuppressWarnings("resource")         Scanner scanner = new Scanner(System.in);         int n = scanner.nextInt();         Port[] p = new Port[n];         for (int i = 0; i < n; i++) {             Port port = new Port();             port.x = scanner.nextInt();             port.y = scanner.nextInt();             p[i] = port;         }         Arrays.sort(p, 0, n, new cmp());                  int max = -1;             for (int i = 0; i < p.length; i++) {             if (p[i].x >max) {                 max = p[i].x;                 System.out.print(p[i].x + " " + p[i].y +"\n");             }         }     }
}