引子

日前,我本身的孤独游玩上部位了,仅此而已,但这是单独欲望。。接下来,我以为找个任务持续。,创业是命中注定的。

在找任务先前,无不阅读少量地实践的的促使。,热更活跃嘛。经过搜索引擎,我在其时的头条逼迫中被发现的人了单独面试成绩。。

标题问题

P为假定的二维立体必不可少的事物的点集。使明确 P 中某点x,假使x目录 P 中任性点都缺少的 x 在右上方区域(程度和铅直被归入同一类别均为GREA,称之为最大的。求出一切“最大的”点的集中。(一切点的横被归入同一类别和纵被归入同一类别都不反复, 被归入同一类别轴的地域为[0], 1e9) 内)

列举如下图:可信赖的点为目录保持健康的点的集中。请使掉转船头信号以查找集中 P 说话中肯一切 ”最大“ 点的集中并出口。

输出刻画:

第不育系输出点集的数字 N, 接下来 N 行,每行两数字字代表点的 X 轴和 Y 轴。

出口刻画:

出口最大 点集中, 因 X 轴出口从小到大,每行两数字字使杰出代表点的 X 轴和 Y轴。

输出示例1
5
1 2
5 3
4 6
7 5
9 0
出口示例1
4 6
7 5
9 0

 思绪

1。强力彻底搜查法

先取一点,和和另一个一切点喻为,看一眼其中的哪一个有点在其右上方,缺乏则显示出该点是“最大点”。反复检测一切的点。不言而喻,算法的错综复杂的状态为O(n)2)

2。异型心理治疗(订购购)

由“最大点”的品质可知,由于每单独“最大点”,若在另一个点的y值大于该点y值,这么另一个点x值必定不足该点的x值。

执意说,当这样的点决定它的x值高于一切y值大于它的点的x值,这么该点执意“最大点” 。网上抚养的答案从根本上说是俱的。。

由于y规则的点集,只必要O(n)那就够了出口“最大点”点集。本喻为的普通排序算法的时期错综复杂的状态O(nlogn)。这么,不言而喻,算法的总体错综复杂的状态为o(nlogn)。

三。减法 异型(过滤 预分类学)

过滤很简略,执意在集中中找出单独喻为好的点,和过滤掉其左下角的一切点。和再采取方式2对过滤后的点集求解。

这么即将到来的集中中喻为好的点,怎地找,或许说哪个点是喻为好的点。不言而喻,越在附近点集右上角的点,左下角的区域越大,越可以过滤更多的点,因而更妥。。

幼年研究,两数字的和,因而两数字字中间的差越小,商品越大。简略设计,该点x和y的和减去x和y差的有无上权力或权威的越大,该点越好。

4。坯分节(最佳化四叉树)

由于我先前学过四叉树。,因而我以为变卖其中的哪一个有四叉树来处置即将到来的成绩。。假使先生熟识kd树,其动机大致如此俱。。 为了最佳化将点集拔出到四叉树的时期,作者应用预翻开的限制来表现四叉树。由于500000个点,所需的大致如此时期列举如下:

build tree cost: 167ms
105233923 999996852
398502327 999994996
837309014 999994263
899779160 999993102
980746971 999976098
990941053 999881685
991773349 999539486
996437667 999536388
999934209 999456481
999948454 989946068
999951793 933115039
999993165 920862637
999996248 471725091
search tree cost: 106ms

授给物点片断量为n,排列第n个矩形查询,第i次查询地域为以第i个点为左下角以记载最大地域为右上角的矩形,若该点右上方缺乏点这么该点为“最大点”。若该点为“最大点”,we的所有格形式也可以用它作为右上角。,以0点位左下角安排地域查询,过滤什么人不必要查询的点。相形之下,we的所有格形式可以看见,查询时期可以接见,但修建起来确凿必要更长的时期。。这可能会理由该方式缺乏被直接地目录。。优秀的时期错综复杂的状态也麝香在O(nlogn)攀登。,佼佼者时期都花在体系妥协上,更多的内存控制将不可推卸地耗费更多的时期。不应用预分类学就可以开腰槽发生。,we的所有格形式的出口与输出按次婚配。,牛口货运网的答案需要量从小到大排序,因而发生必不可少的事物重行排序。。。假使发生集高度地大,排序发生集必要破费落落大方时期。很同情,四叉树量度损失,率先,C的输出和出口将职业落落大方时期。,其次,we的所有格形式必要对发生集重行排序。但试验显示出了由于随机500000点,应用四叉树可以和预排序富国事实上的时期错综复杂的状态。不可更改的,而且单独要紧的有责任成绩。:

int x=999999991;float y = 1000000000f;float z = x/y;

Z值是多少?答案是必然的。,由于浮点数不敷正确,无法表达,因而它扩展了,即将到来的成绩一经让我的四叉树以为单独小概率是abno。花了良久时期才把它拔摆脱。。

附加信号,备忘。

using System.IO;
using System;
using System.Collections.Generic;
using System.Diagnostics;
class Program
{
    privatestaticint maxData = 1000000000;
    privatestatic List 记载点 = new List();
    privatestatic Random rand = new Random();
    staticvoid Main()
    {
      
        float time = 0;
        Stopwatch watch = new Stopwatch();
        ();
        
        Quadtree quad = new Quadtree(5, new Rectangle(0, 0, maxData, maxData));
      
        int count = int.Parse(());
    
        for (int i = 0; i < count; i++)
        {
            MyPoint temp;
            //string[] inputs = ().Split(new char[] { '' '' });
            //temp.x = 替换.toint32(输出[0]
            //temp.y = 替换.toint32(输出[1]
            temp.x = rand.Next(maxData);
            temp.y = rand.Next(maxData);
            (暂时)
            (暂时)
        }
        time = watch.ElapsedMilliseconds - time;
        ("build tree cost: " + time + "ms");
        List result = new List();
        Rectangle rect;
         = rect.height = maxData + 1;
       
        for (int i = 0; i < count; i++)
        {
           
            rect.x = 记载点[i].x;
            rect.y = 记载点[i].y;
            if ((RCT))
            {
                continue;
            }
            (记载点[i]);
           
        }
        //从小到大的X轴Y出口,因而发生集必要排序        ();
        for(int i=0;i< result.Count; i++)
        {
            ( 发生[I]
        }
        time = watch.ElapsedMilliseconds - time;
        ("search tree cost: " + time + "ms");
        ();
    }
}


publicclass Quadtree
{
    privateclass QuadtreeData
    {
        publicint maxLevel;
        publicdouble maxWidth;
        publicdouble maxHeight;
        public Quadtree[] allNodes;
        public QuadtreeData(int maxLevel,float maxWidth,float maxHeight)
        {
            this.maxLevel = maxLevel;
            this.maxWidth = maxWidth;
            this.maxHeight = maxHeight;
            
            int maxNodes = 0;
            for (int i = 0; i <= maxLevel; i++)
            {
                maxNodes += (int)(4, i);
            }
            allNodes = new Quadtree[maxNodes];
           
        }
    }

    privateint level;
    privateint parent;
    privateint count;
    private List points;
    private Rectangle bounds;
    private Quadtree[] nodes;
    private QuadtreeData data;
    
    public Quadtree(int maxLevel,Rectangle bounds)
    {
        data = new QuadtreeData(maxLevel,);
        this.bounds = bounds;
        level = 0;
        count = 0;
        parent = -1;
        nodes = new Quadtree[4];
        Init();
    }

    privatevoid Init()
    {
        
        [0] = this;
       
        for (int i = 0; i < .Length; i++)
        {
            if ([i].level >= )
                break;
            InitChildrenNew(i);
        }

    }
    privatevoid InitChildrenNew(int parentIndex)
    {
       
        Rectangle bounds = [parentIndex].bounds;
        float subWidth = (() / 2);
        float subHeight = (() / 2);
        float x = ();
        float y = ();
        
        int nextLevel =  [parentIndex].level + 1;
        byte[,] offset =newbyte[,]{{0,0},{1,0},{0,1},{1,1}};
        for (int i = 0; i < 4; i++)
        {
            Rectangle rect = new Rectangle(x,y,subWidth,subHeight);
            
            rect.x += offset[i,0]*subWidth;
            rect.y += offset[i,1]*subHeight;
            
            int childIndex = GetPointIndexByLevel((), nextLevel);
            if (childIndex < .Length)
            {
                [childIndex] = new Quadtree(nextLevel, rect, data);
                [childIndex].parent = parentIndex;
                [parentIndex].nodes[i] = [childIndex];
                //("p:"+parentIndex+",c:"+childIndex+",size:"+ );            }



        }
    }
  
    
    private Quadtree(int pLevel, Rectangle pBounds , QuadtreeData pData)
    {
        level = pLevel;
        bounds = pBounds;
        nodes = new Quadtree[4];
        count = 0;
        data = pData;
    }
  
   

    publicint GetPointIndexByLevel(MyPoint point, int targetLevel)
    {
       
        int[] indexByLevel={0,1,5,21,85,341,1365,5461,21845};
        int startIndex =indexByLevel[targetLevel] ;
        
        int cc = (int)(2, targetLevel);
        
        //if(point.x >= data.maxWidth || point.y >=)
        //{
        //    ("error point:"+point);
        //    ("data:"+","+);
        //}int locationX = (int)(point.x / data.maxWidth * cc);
        int locationY = (int)(point.y /  * cc);
        int idx = startIndex + locationY * cc + locationX;
        
        return idx;
    }
    /*
    * Insert the object into the quadtree. If the node
    * exceeds the capacity, it will split and add all
    * objects to their corresponding nodes.
    */publicvoid Insert(MyPoint point)
    {

        int idx = GetPointIndexByLevel(point, );

        var nodeToAdd = [idx];
       
        if (nodeToAdd != null)
        {
            
            if (nodeToAdd.points == null)
                   nodeToAdd.points = new List();
            
            (point);
            ();
            
        }
        
    }
    privatevoid AddCount()
    {
        if(parent >=0 )
        {
             var nodeParent = [parent];
             ();
        }
        count++;
    }

    /*
    * Return all objects that could collide with the given object
    */publicbool retrieve(Rectangle pRect)
    {
       
        if(count > 0 && (bounds))
        {
            returntrue;
        }
          
        if(count > 0 && (pRect))
        {
            
            if (points != null)
            {
              
                for (int i = 0; i < points.Count; i++)
                {
                  
                    if ((points[i]))
                    {
                        returntrue;
                    }

                }
            }

            elseif (level < )
            {
               
                if (nodes[3] != null && nodes[3].retrieve(pRect)) returntrue;
                if (nodes[2] != null && nodes[2].retrieve(pRect)) returntrue;
                if (nodes[1] != null && nodes[1].retrieve(pRect)) returntrue;
                if (nodes[0] != null && nodes[0].retrieve(pRect)) returntrue;
            }

        }

        returnfalse;

    }

   
}

publicstruct MyPoint : IComparable
{
    publicint x;
    publicint y;
    public MyPoint(int x = 0, int y = 0)
    {
        this.x = x;
        this.y = y;
    }

    publicoverridestring ToString()
    {
        return  x + "" + y;
    }
    publicint CompareTo(MyPoint 另一个)
    {
        if(x == )
          return0;
        elseif(x > )
          return1;
        elseif( x < )
          return -1;
         
         return -1;
    }
}
publicstruct Rectangle
{
    publicfloat x;
    publicfloat y;
    publicfloat height;
    publicfloat width;
    public Rectangle(float x = 0, float y = 0, float width = 0, float height = 0)
    {
        this.x = x;
        this.y = y;
        this.width = width;
        this.height = height;
    }
    publicfloat getX() { return x; }
    publicfloat getY() { return y; }
    publicfloat getHeight() { return height; }
    publicfloat getWidth() { return width; }
    public MyPoint getCenter() { returnnew MyPoint((int)(x + width / 2), (int)(y + height / 2)); }
    publicbool Intersects(Rectangle Rect)
    {
        return (!(y > Rect.y + Rect.height ||
                   y + height < Rect.y ||
                   x + width < Rect.x ||
                   x > Rect.x + Rect.width));
    }
    publicbool Contains(MyPoint point)
    {
        return (x < point.x && x + width >= point.x &&
                y < point.y && y + height >= point.y);
    }
    
    publicbool 包括(矩形 另一个)
    {
        return Contains(new MyPoint((int),(int))) 
        && Contains(new MyPoint((int)(+other.width),(int)(+other.height)));
    }

    publicoverridestring ToString()
    {
        return"Rect:" + x + "," + y + "," + width;
    }
}

过滤与直接地预排序天平使掉转船头

#include
#include
#include
#include 
#include 
usingnamespace std;
struct point{     //使明确妥协int x,y;
};
bool 两人间的关系机械抛光(点) a,point b){  //自使明确排序方式return a.y==b.y?a.x>b.x:a.y//Y升序,x降序排列}
int main(){
    clock_t start,finish;
    double totaltime;
    std::srand(std::time(nullptr)); // use current time as seed for random generatorint count;  
    cout<<"输出点的数字和点:" ;
    cin>>count;
cout<<"输出总点数为:"< p; //侦查用来装立体上的点for(int i=0;i){ point temp; temp.x
= std::rand()% 100000000; temp.y = std::rand()% 100000000; (暂时) //为了手巧的天平机能,we的所有格形式随机拔出落落大方点 }

cout<<"过滤后应用预排序:------------------------------"<<endl; start

= clock(); vector filter;//使明确屏幕侦查 vector res; //使明确发生侦查int curMaxRank = 0; int curMaxIndex = 0; for(int i=0;i){ int temp P[I].X P[I].Y-Std::Abs(P[I].X)p[i].y); if(发烧) > curMaxRank) { curMaxRank = temp; curMaxIndex = i; } } for(int i=0;i) { if(p[i].x >= p[curMaxIndex].x || p[i].y>= p[curMaxIndex].y) { (p[i]); } } sort((),(),两人间的关系机械抛光) (否决者-1]); //左上角的引出各种从句点,必然的资历int maxx=filter[()-1].x; for(int i=()-2;i>=0;i--){ //Y从大到小,若i点x值大于一切比其y值大的点的x值,这么i点为“最大点”。if(否决者[i] x>maxx){ (否决者) maxx=filter[i].x; } } finish = clock(); cout<<"过滤后点总计:"<<()<<endl; cout<<"适合保持健康的点总计:"<<()<<endl; for(int i=0;i<();i++){ printf("%d %d\n", res[i].x, res[i].y); } totaltime=(double)(finish-start)/CLOCKS_PER_SEC; cout<<"n该顺序的运转时期为"<"秒!"<<endl; cout<<"直接地应用预分类学:------------------------------"<<endl; start = clock(); sort((),(),两人间的关系机械抛光) (); (p[()-1]); //左上角的引出各种从句点,必然的资历int maxX=p[()-1].x; for(int i=()-2;i>=0;i--){ //Y从大到小,若i点x值大于一切比其y值大的点的x值,这么i点为“最大点”。if(p[i].x>maxX){ (p[i]); maxX=p[i].x; } } finish = clock(); cout<<"适合保持健康的点总计:"<<()<<endl; for(int i=0;i<();i++){ printf("%d %d\n", res[i].x, res[i].y); } totaltime=(double)(finish-start)/CLOCKS_PER_SEC; cout<<"n该顺序的运转时期为"<"秒!"<<endl; return0; }
输出点的数字和点:......输出总点数为:500000
过滤后应用预排序:------------------------------
过滤后点总计:648
适合保持健康的点总计:16
15480205 99999697
17427518 99999676
78059606 99999351
80881235 99998746
91608165 99997683
95825638 99996289
99690315 99993155
99874266 99991089
99884382 99978546
99908259 99961095
99942330 99858670
99963997 99157830
99975627 97385053
99996564 95654979
99998236 95378376
99999527 66461920

即将到来的顺序几秒钟后运转!
直接地应用预分类学:------------------------------
适合保持健康的点总计:16
15480205 99999697
17427518 99999676
78059606 99999351
80881235 99998746
91608165 99997683
95825638 99996289
99690315 99993155
99874266 99991089
99884382 99978546
99908259 99961095
99942330 99858670
99963997 99157830
99975627 97385053
99996564 95654979
99998236 95378376
99999527 66461920

即将到来的顺序几秒钟后运转!

可以在niuke.com上量度以下信号

#include
#include
#include
#include 

usingnamespace std;
struct point{     //使明确妥协int x,y;
};
bool 两人间的关系机械抛光(点) a,point b){  //自使明确排序方式return a.y==b.y?a.x>b.x:a.y//Y升序,x降序排列}
point p[500001];
point filter[500001];
int main(){
    
    int count;  
   
    scanf("%d",&伯爵)
   
    
    for(int i = 0; i < count; i++)
    {
       scanf("%d%d", &p[i].x, &p[i].y);
    }

  
  
    int curMaxRank = 0;
    int curMaxIndex = 0;
    for(int i=0;i){
        int temp P[I].X P[I].Y-Std::Abs(P[I].X)p[i].y);
        if(发烧) > curMaxRank)
        {
            curMaxRank = temp;
            curMaxIndex = i;
        }
    }
    int fCount =0 ;
    for(int i=0;i)
    {
        if(p[i].x >= p[curMaxIndex].x || p[i].y>= p[curMaxIndex].y)
        {
            filter[fCount++]=p[i];
        }
    }
    
    排序(过滤),filter+fCount,两人间的关系机械抛光)
    
    int maxx=-1;
    for(int i=fCount-1;i>=0;i--){  //Y从大到小,若i点x值大于一切比其y值大的点的x值,这么i点为“最大点”。if(否决者[i] x>maxx){
           
            printf("%d %d\n", filter[i].x, filter[i].y);
            maxx=filter[i].x;
        }
    }
   
   
    return0;
}

经过时期约为200-300 ms,事实上与直接地订购购俱,因而牛科丸的检测参考资料麝香是喻为特别的。,过滤产生坏的,或许输出和出口职业佼佼者时期,归根结蒂,最佳化算法不克不及增加誊写版印刷品时期。。。。不外更不用说,由于随机的用例,we的所有格形式可以确保算法会更妥。。

总结与预测

由于随机点做很多量度,找寻作者抚养的滤波方式的在性,几何平均可以过滤的点。也执意说过滤后所剩点m的总计为原始点集n总计的杰出。

应用过滤的额定健全的是,we的所有格形式只必要开拓杰出的内存,和就可以不变换原有点集的按次,也执意说假使标题问题而且不变换原有点集的需要量,仍然可以目录 。

过滤开支的时期定价是直线的的。这么算法的全面错综复杂的状态为O(n+ mlogm),普通m值是n的杰出。。则算法的几何平均错综复杂的状态为o(n),坯错综复杂的状态o(m)。经过超过信号的实践喻为,机能高处了20倍摆布。。应用O(M)坯,可以确保不变换原有点集的按次。 we的所有格形式能持续最佳化吗?,可以可以,最佳化永久的,假如你不轻轻地废思索。

本文对四叉树的记载妥协停止了重申,以处理这一成绩。,由于随机量度点也有不离儿的机能。

假使它能扶助你,点个赞呗~  原件文字,请勿转载,道谢的话

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注