首页 > 试题广场 >

输出点集合

[编程题]输出点集合

热度指数：19300 时间限制：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

算法知识视频讲解

牛客网史上最菜菜鸟

//按照y值从大到小排序，然后扫描，保存当前最大的x，如果该点比x大，那么该点满足条件
//注意要使用scanf,printf,使用cin,cout会超时

#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
struct node{
    int x;
    int y;
};

bool cmp(node n1, node n2){
    return n1.y>n2.y;
}
node no[500001];
int main(){
    int n;
    while(scanf("%d", &n)!=EOF){
        for(int i = 0; i < n; i++)
        {
            scanf("%d%d", &no[i].x, &no[i].y);
        }
        sort(no,no+n,cmp);
        int mmax = -1;
        for(int i = 0; i < n; i++)
        {
            if(no[i].x>mmax)
            {
                mmax=no[i].x;
                printf("%d %d\n", no[i].x ,no[i].y);
            }
        }

    }
    return 0;
}

发表于 2018-07-03 23:47:28 回复(7)

开心的米奇

python只能过80%的数据,麻烦管理修改内存！

发表于 2019-04-13 15:45:43 回复(7)

国王的冕冠

一个点右上方没有点，也就是一个点右边的点全都在它的下边。
所以我们将点按照横坐标从左到右排序，从右开始扫，找出右边点最大纵坐标。
那么一个点的纵坐标比右边的点纵坐标最大值还大，就说明这个点右边的点全在它的下面。
这样选择点就可以选出所有符合条件的点了。
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pr make_pair
#define fi first
#define se second
const int MAX_N = 5e5 + 5;
typedef pair<int, int> pii;
vector<pii> p;
pii ans[MAX_N];
int main() {
    int n, x, y, num, limit;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &x, &y);
        p.pb(pr(x, y));
    }
    sort(p.begin(), p.end());
    num = 0, limit = -1;
    for (int i = n - 1; i >= 0; i--) {
        if (p[i].se > limit) {
            ans[num] = p[i];
            num++;
            limit = p[i].se;
        }
    }
    for (int i = num - 1; i >= 0; i--) {
        printf("%d %d\n", ans[i].fi, ans[i].se);
    }
    return 0;
}

发表于 2018-02-04 13:39:13 回复(3)

菜鸟一号。

C++
//倒序查找法，通过率100%
//暴力破解法,因为超时，通过率只到60%，

#include<iostream>
#include<vector>
#include<algorithm>
usingnamespacestd;
intmain()
{
intN;
cin >> N;
intx, y;
vector<pair<int, int>>point(N);
for(inti = 0; i < N; i++)
{
cin >> x >> y;
point[i] = make_pair(x,y);
}
sort(point.begin(),point.end());
//倒序查找法100%
intMax=point[N-1].second;
vector<int>a(N);
a[N-1]=1;
for(inti=N-2;i>=0;i--)
{
if(point[i].second>Max)
a[i]=1;
Max=max(point[i].second,Max);
}
for(inti=0;i<N;i++)
{
if(a[i]==1)
cout<<point[i].first<<" "<<point[i].second<<endl;
}
//暴力破解，超时，60%
//for (int i = 0; i < N-1; i++)
//{
// int n = 1;
// for (int j = i+1; j < N; j++)
//{
// if (point[i].second < point[j].second)
// {
//   n = 0;
// break;
// }
//  }
// if (n == 1)
// cout << point[i].first<<" " << point[i].second << endl;
//}
//cout << point[N-1].first<<" " << point[N-1].second << endl;
return0;
}

编辑于 2020-06-28 19:55:37 回复(1)

wjt0103

import sys
if __name__=="__main__":
    N = sys.stdin.readline().strip('\n')
    N = int(N)
    P = []
    output = []
    for i in range(N):
        x,y = sys.stdin.readline().strip('\n').split(' ')
        P.append([int(x),int(y)])
    P.sort(reverse=True)
    MAXX = 0
    MAXY = 0

    for m,n in P:
        if m > MAXX or n > MAXY:
            MAXX = m
            MAXY = n
            output.append([m, n])
    output.sort()
    for m,n in output:
        print(m,n)

发表于 2018-08-23 11:14:28 回复(1)

April-6

import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;

public class Main0 {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int a[] = new int[n];
        int b[] = new int[n];
        for(int i=0; i<n; i++){
            a[i] = in.nextInt();
            b[i] = in.nextInt();
        }
        int maxY = b[n-1];
        for(int i=n-2; i>=0; i--){
            if(b[i]>maxY){
                System.out.println(a[i]+" "+b[i]);
            }
        }
        System.out.println(a[n-1]+" "+b[n-1]);

    }

}

发表于 2018-04-14 21:33:28 回复(2)

我是管小亮

#include<bits/stdc++.h>
using namespace std;
bool cmp(const pair<int, int> &a,const pair<int, int> &b){
    return a.first>b.first;
}
int main(){
    int n;
    while(EOF != scanf("%d", &n)){
        vector<pair<int,int>> arr;
        for(int i=0,x,y;i<n;++i){
            scanf("%d %d", &x, &y);
            arr.emplace_back(x,y);
        }
        sort(arr.begin(),arr.end(),cmp);
        vector<pair<int,int>> ans;
        for(int i=0,maxNum;i<n;++i){
            if(arr[i].second>maxNum){
                ans.push_back(arr[i]);
                maxNum=arr[i].second;
            }
        }
        for(auto it=ans.rbegin();it!=ans.rend();++it){
            printf("%d %d\n", it->first, it->second);
        }
    }
    
    return 0;
}

几个点：

1、按 x 轴坐标从大到小排序，这是为了保证遍历过的点都在当前点的右边；

2、遍历的时候维护一个最大的 y 轴坐标；

3、如果新坐标的 y 值大于 maxNum，则上方没点；

4、从大到小排序，ans也是从大到小排序，输出需要逆序；

编辑于 2020-08-06 22:56:00 回复(0)

SuperAidenGreen

没有vector的日子，想它 :(

#include<iostream>
#include<algorithm>

using namespace std;

int main() {
	bool cmp(int *p, int *q);
	int eNum = 0;
	scanf("%d", &eNum);
	int** samples;
	samples = new int*[eNum];
	for (int i = 0; i < eNum; i++) {
		samples[i] = new int[2];
		scanf("%d %d", &samples[i][0], &samples[i][1]);
	}
	sort(samples, samples + eNum,cmp);
	int max = samples[eNum - 1][0];
	for (int i = eNum - 1; i >= 0; i--) {
		if (samples[i][0] >= max) {
			printf("%d %d\n", samples[i][0], samples[i][1]);
			max = samples[i][0];
		}
	}
}
bool cmp(int *p, int *q)
{
	return p[1] < q[1];
}

发表于 2019-09-17 21:19:24 回复(1)

现在是CookbookTime

/* 
 * 更新一个cout不超时的版本 ~=~
 */

#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
struct point
{
    int x;
    int y;
};
 
bool compare(struct point x, struct point y)
{
    return x.y > y.y;
}
 
int main()
{
    int N;
    while (cin >> N)
    {
        int x = 0, y = 0, tmp = 0;
        vector<struct point> vc;
        for (auto i = 0; i < N; i++)
        {
            struct point p;
            cin >> x >> y;
            p.x = x, p.y = y;
            vc.push_back(p);
        }
         
        sort(vc.begin(), vc.end(), compare);
         
        tmp = vc[0].x;
         
        for (auto i = 0; i < vc.size(); i++)
        {
            if (tmp <= vc[i].x)
            {
                tmp = vc[i].x;
                cout << vc[i].x << " " << vc[i].y << '\n';
            }
        }
    }
    return 0;
}

编辑于 2019-08-08 08:56:53 回复(1)

海滩上种花

import sys 
points = []
for line in sys.stdin:
    lin = line.split()
    if len(lin)==1:
        continue
    else:
        points.append((int(lin[0]),int(lin[1])))
points.sort(reverse=True, key=lambda x:x[1])
#res.append(nums[0])
flag_x = points[0][0]
print(str(points[0][0])+' '+str(points[0][1]))
for p in points:
    if p[0]>flag_x:
        #res.append(p)
        print(str(p[0])+' '+str(p[1]))
        flag_x = p[0]
    else:
        continue
#只能通过80%，有大神帮忙瞅一眼吗？超内存。。

发表于 2019-03-14 22:54:17 回复(5)

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)

Python

牛客281466339号

测试case预期结果是默认的Y值倒序，不是输入的顺序，不符合这个顺序就判定不成功，这个设计是否合理，题目只是找出点的集合，并没有规定顺序。

ps：有没有python通过了，既不超时也没超内存的

编辑于 2021-05-23 17:53:20 回复(2)

Yeira

按照x从大到小排序

最右边的y可以小与其他的，其余的y一定要比他右边的大，因此要从右往左遍历

发表于 2021-05-09 11:01:43 回复(0)

醉清风951

#include "iostream"
#include "stdio.h"
#include "algorithm"
using namespace std;
 
struct point{
    int x,y;
}p[500001];
 
int cmp1(const point &a,const point &b){
    return a.y > b.y;
}
 
int main(){
    int n,i,j,x,y;
    scanf("%d",&n);
    for(i = 0;i < n; i++)
        scanf("%d %d",&p[i].x,&p[i].y);
    sort(p,p+n,cmp1);
    int Max = p[0].x;
    printf("%d %d\n",p[0].x,p[0].y);
    for(i = 0;i < n; i++){
        if(p[i].x > Max){
            Max = p[i].x;
            printf("%d %d\n",p[i].x,p[i].y);
        }
    }
    return 0;
}

发表于 2019-09-16 16:01:09 回复(0)

已注销

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 5e5 + 10;

struct point
{
    int x, y;
};

int n, cnt;
point pts[MAXN];
point res[MAXN];

bool cmp(const point &a, const point &b)
{
    return a.x < b.x;
}

void solve()
{
    sort(pts, pts + n, cmp);

    res[0] = pts[n - 1];
    int mx = res[0].y;
    cnt = 1;
    for (int i = n - 2; i >= 0; i--)
    {
        if (pts[i].y >= mx)
        {
            res[cnt++] = pts[i];
            mx = pts[i].y;
        }
    }
}

int main()
{
    cin >> n;

    for (int i = 0; i < n; i++)
    {
        scanf("%d%d", &pts[i].x, &pts[i].y);
    }

    solve();

    for (int i = cnt - 1; i >= 0; i--)
    {
        printf("%d %d\n", res[i].x, res[i].y);
    }

    return 0;
}

发表于 2018-01-26 17:38:08 回复(0)

弄莲子

？？？为什么粘贴过来还翻译成中文了？？？ # 这份代码自测数据就能通过，提交时的测试数据（每个数都是六七位的）就不能过（哭哭 n = int(input()) x = [] y = [] for i in range(n): x1, y1 = input().split() x.append(int(x1)) y.append(int(y1)) dict1 = dict(zip(x, y)) # print(dict1) # n = 5 # x = [1,5,4,7,9] # y = [2,3,6,5,0] # dict1 = {1: 2, 5: 3, 4: 6, 7: 5, 9: 0} # 判断i在j的左右 for i in range(n): for j in range(i + 1, n): # 1 i在j左边（i，j） xi = x[i] xj = x[j] yi = y[i] yj = y[j] if xi < xj: # 判断i在j的上下 # y[i]>y[j] i 在j上左上 if yi > yj: # 保留i点 pass # y[i]<y>y[j] i 在j上右上 if yi > yj: # 删除 j 点 dict1.pop(xj) break # y[i]</y>

发表于 2023-03-19 21:06:52 回复(0)

学废了的胖子

每个点按照x维从大到小排序，然后倒序遍历比较y维数值最大值，最后最大值变化次数即为答案。

发表于 2023-02-11 20:31:30 回复(0)

BuTou1030

// 为啥下面代码一个用例都过不了呢，求解
package main

import (
    "fmt"
    "bufio"
    "os"
    "strings"
    "strconv"
)

func main() {
    sc := bufio.NewScanner(os.Stdin)
    bs := make([]byte, 1024 * 1024 * 64)
    sc.Buffer(bs, len(bs))
    
    for k := 0; k < 10; k ++ {
        sc.Scan()
        n, _ := strconv.Atoi(sc.Text())
        nums := make([]int, n)
        sc.Scan()
        line2 := strings.Fields(sc.Text())
        for i, l2 := range line2 {
            nums[i], _ = strconv.Atoi(l2)
        }

        maxV := 0
        for i, cur := range nums {
            sum := cur
            for j := i-1; j >= 0; j -- {
                if nums[j] >= cur {
                    sum += nums[j]
                } else {
                    break
                }
            }
            for j := i+1; j < n; j ++ {
                if nums[j] >= cur {
                    sum += nums[j]
                } else {
                    break
                }
            }
            maxV = max(maxV, cur * sum)
        }

        fmt.Println(maxV)
    }
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

发表于 2022-08-14 14:33:16 回复(0)

流心汤圆

有没有人帮我解释一下呀😭😭 # def jihe()
num = int(input())
jihe = []
for n in range(0,num):
    l = list(map(int,input().split()))
    jihe.append(l)
# print(jihe)
jihe1 = jihe[:]
for i in jihe1:
    for j in jihe1:
        if j[0]>i[0] and j[1]>i[1]:
            jihe.remove(i)
            break
# print(jihe)
for a in jihe:
    print(a[0],a[1])

发表于 2022-07-19 10:32:11 回复(0)

整顿职场的螺狮粉很忙碌

# name：LH
# 2022/4/2 13:00

point = []
refer_num = 0
while True:
    str_re = input('请输入参照数字(要求为正整数，n或N退出)：')
    if str_re == 'n'&nbs***bsp;str_re == 'N':
        break
    else:
        try:
            int_re = int(str_re)
        except Exception as re_err:
            print(f'{re_err}\n输入有误,请重新输入！')
        else:
            refer_num = int_re
            break
while True:
    str_p = input('请输入坐标点的横坐标x和纵坐标y(要求：1、横纵坐标都为正整数；'
                  '2、x y使用英文","间隔；3、回车确认；4、输入n或N并回车->结束。'
                  '（示例：5,7）\n请输入：')
    if str_p == 'n'&nbs***bsp;str_p == 'N':
        break
    else:
        try:
            temp = str_p.split(',', 1)
            temp[0] = int(temp[0])
            temp[1] = int(temp[1])
        except Exception as p_err:
            print(f'{p_err}\n输入有误，请重新输入!')
            continue
        else:
            point.append(temp)
        finally:
            print('*'*120)

point.sort()

max_point = []
i = 0
while i < len(point):
    if point[i][0] > refer_num&nbs***bsp;point[i][1] > refer_num:
        max_point.append(point[i])
    i += 1

print(max_point)

发表于 2022-04-02 15:08:46 回复(0)

提交观点

问题信息

测试开发工程师测试工程师 2018 字节跳动数学排序

上传者：小小

难度：

78条回答 549收藏 28348浏览

通过挑战的用户

查看代码

zhangbw_

2023-02-28 12:19:06
ingram14

2023-01-29 16:47:17
jiaming...

2022-12-07 19:04:00
qqwwer777

2022-11-13 13:31:05
clwycash

2022-11-12 20:43:43