题目3-点的集合.md

题目来源:

题目描述：

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

输入

输出

解题思路：

根据题目中的 code>如果x满足 P 中任意点都不在 x 的右上方区域内（横纵坐标都大于x） 的等价描述为 code>x至少有一个坐标比剩余的点的坐标大 。那么我们先把所有点的某一个方向的坐标按照从小到大的排列，然后从后向前遍历，该点的另一个坐标，要比遍历过的大,那么该点就是最大点。

代码实现:

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159


#include<iostream>
#include<vector>

//定义点
struct Point
{
    explicit Point(const int x,const int y){
        m_x=x;
        m_y=y;
    }
    int m_x;
    int m_y;
};

//Point的X坐标比较函数
bool PointLessX(const Point& lhs,const Point& rhs)
{
    return lhs.m_x  < rhs.m_x;
}

//Point的Y坐标比较函数
bool PointLessY(const Point& lhs,const Point& rhs)
{
    return lhs.m_y  < rhs.m_y;
}

//获取点的X坐标
int GetX(const Point pt)
{
    return pt.m_x;
}

//获取点的Y坐标
int GetY(const Point pt)
{
    return pt.m_y;
}

//先对X坐标排序，然后根据Y坐标选择点
std::vector<Point> GetMaxPointSetByX(std::vector Point> pointVec)
{
    std::vector<Point> resultVec;
    if(pointVec.empty())
    {
        return resultVec;
    }
    else
    {
        std::sort(pointVec.begin(),pointVec.end(),PointLessX);
        int curMaxY = pointVec.rbegin()->m_y;
        resultVec.push_back(*pointVec.rbegin());
        for(auto item = pointVec.rbegin(); item != pointVec.rend() ; item++)
        {
            if(item->m_y > curMaxY)
            {
                curMaxY = item->m_y;
                resultVec.push_back(*item);
            }
        }
        return resultVec;
    }
}

//先对点的Y坐标排序，然后根据X坐标筛选点
std::vector<Point> GetMaxPointSetByY(std::vector Point> pointVec)
{
    std::vector<Point> resultVec;
    if(pointVec.empty())
    {
        return resultVec;
    }
    else
    {
        //Y坐标排序
        std::sort(pointVec.begin(),pointVec.end(),PointLessY);
        //X坐标选点
        int curMaxX = pointVec.rbegin()->m_x;
        resultVec.push_back(*pointVec.rbegin());
        for(auto item = pointVec.rbegin(); item != pointVec.rend() ; item++)
        {
            if(item->m_x > curMaxX)
            {
                curMaxX = item->m_x;
                resultVec.push_back(*item);
            }
        }
        return resultVec;
    }
}


//定义函数指针
using FuncCompare = decltype(PointLessX);
using FuncGetValue = decltype(GetX); 

//根据GetMaxPointSetByX和GetMaxPointSetByY，总结出的函数模板
std::vector<Point> GetMaxPointSetByTemplate(std::vector Point> pointVec,FuncCompare compare,FuncGetValue getValue)
{
    std::vector<Point> resultVec;
    if(pointVec.empty())
    {
        return resultVec;
    }
    else
    {
        std::sort(pointVec.begin(),pointVec.end(),compare);
        int curMaxValue = getValue(*pointVec.rbegin());
        resultVec.push_back(*pointVec.rbegin());
        for(auto item = pointVec.rbegin(); item != pointVec.rend() ; item++)
        {
            if(getValue(*item) > curMaxValue)
            {
                curMaxValue = getValue(*item);
                resultVec.push_back(*item);
            }
        }
        return resultVec;
    }
}


int main(int argc,char * argv[])
{
    std::vector<Point> pointVec;
    pointVec.push_back(Point(1,2));
    pointVec.push_back(Point(5,3));
    pointVec.push_back(Point(4,6)),
    pointVec.push_back(Point(7,5));
    pointVec.push_back(Point(9,0));


    auto result = GetMaxPointSetByX(pointVec);
    std::cout << "-------------- Method One -------" <<  std::endl;
    for(const auto& item:result)
    {
        std::cout<<   item.m_x <<  "  " <<  item. m_y  << std::endl;
    }

    auto resultByY = GetMaxPointSetByY(pointVec);
    std::cout <<  "-------------- Method Two -------" <<  std::endl;
    for(const auto& item:resultByY)
    {
        std::cout <<  item.m_x <<  "  " <<  item. m_y <<  std::endl;
    }

    std::cout <<  "-------------- Method Three -------------" <<  std::endl;
    auto resultThree = GetMaxPointSetByTemplate(pointVec,PointLessX,GetY);
    for(const auto& item:resultThree)
    {
        std::cout <<  item.m_x <<  "  " <<  item. m_y  << std::endl;
    }
    std::cout <<  "-------------- Method Four -------------" <<  std::endl;
    auto resultFour = GetMaxPointSetByTemplate(pointVec,PointLessY,GetX);
    for(const auto& item:resultFour)
    {
        std::cout  << item.m_x  << "  " <<  item. m_y <<  std::endl;
    }
    return 0;
}

代码精讲：

本次的题目比较简单，代码中比较有意思的是根据前面的两个函数，总结出的函数模板，这样的方法跟std::sort很类似。

文章目录