首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

分治法求最近问题

蛮力法 算法思想 蛮力法,顾名思义,即穷举所有点与之间的距离,两层循环暴力找出最近算法执行可视化如图1所示,word文档GIF静态显示,附件已含动图。...分治算法思想 先进行预处理按横坐标排序,然后每次将均分成左右两个子集,最短距离的两个要么都在左子集,要么都在右子集,要么一个点在左子集中,一个点在右子集中,对于前面两种情况,问题变成递归寻找子集的最短距离...,算法执行可视化如图3所示,word文档GIF静态显示,附件已含动图。...图4 如果存在最短距离,那么一定是一边一个,所以我们需要将两边的距离算一下,实际上,我们需要对于一边的,我们需要计算距离的最多不超过4个,因为同一边的之间的距离肯定大于等于minDistance...图10 分析: 由实验结果可知,在分治规模小于一定数量时采用暴力求解效率更快,特别是在数据规模大的时候,这种暴力分治相结合的方法相比原始分治法具有很大的优势。

20920

分治应用--最近问题 & POJ 3714

问题描述 二维平面上有n个,如何快速计算出两个距离最近? 2....解题思路 暴力做法是,每个与其他去计算距离,取最小的出来,复杂度O(n2) 采用分治算法 将数据点按照 x 坐标排序,找到中位,过中位划线 x = mid_x 将数据分成2部分,递归划分,直到两个半边只有...范围内的左右才有可能距离比 d 更小(好理解) 这个范围内的,再按照 y 坐标排序,查找两个的 y 差值小于 d 的(重点在这里,见下面分析),计算其距离是否比 d 更小 ?...假如在这个范围内的有1,2,3,4,5,6六个(按 y 坐标排序),寻找距离小于 d 的,如果暴力查找,复杂度还是 n2,我们可以看出点4只有可能在其上下y坐标 ± d 的范围内找到满足距离小于...实现代码 /** * @description: 2维平面寻找距离最近分治) * @author: michael ming * @date: 2019/7/4 23:16 * @modified

82710
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    原 初学算法-分治法求平面上最近(Cl

    本来这个算法在笔者电脑里无人问津过一段时间了,但今天正好做HDU 1007见到了这个问题,今天就来把代码分享出来吧!     ...那么最短距离一定在左半部分、右半部分、跨越左右的中的一个。      那么你可能会有疑问了:本来最近也一定在这三个区域内,这不还是相当于什么都没干吗?     还真不是。...我们可以假设通过递归得到了左边最小距离为d1,右边最小距离为d2,令δ = min(d1,d2)     如图所示,如果跨越左右的可能是最短距离,那么它也必然比δ小。...另外,可以证明对于每个矩形区域,最多尝试8个一定能找到最短距离(算法导论第33.4节有详细的证明,这里不再赘述)。     ...下面,通过这个算法,我们就可以写出一份代码来: /**  * Find closest distance in N points.

    1.5K150

    计算几何 平面最近 nlogn分治算法 求平面中距离最近的两

    平面最近,即平面中距离最近的两 分治算法: int SOLVE(int left,int right)//求解集中区间[left,right]中的最近 { double ans...分析当前集合[left,right]中的最近,有两种可能: 1....当前集合中的最近的两同属于集合[left,mid]或同属于集合[mid,right] 则ans = min(集合1中所有点的最近距离, 集合2中所有点的最近距离...于是我们可以对temp以y为唯一关键字从小到大排序,进行枚举, 更新ans,然后在枚举时判断:一旦枚举到的与py值之差大于ans,停止枚举。最后就能得到该区间的最近。...return sqrt ( (double) ( (a.x - b.x ) * ( a.x - b.x ) + ( a.y - b.y ) * ( a.y - b.y ) ) ); } /*分治法求计算几何中平面点最近距离

    2.6K20

    hdu1007平面最近分治

    题目大意:给你N,求这N点中两队的距离的一半,精确到小数点后两位 暴力显然O(n^2),不能过。 分治即可,N,求中间值,mid。...按照横坐标升序排列,递归求出0到mid以及mid+1到N-1的最小距离。 分治关键步骤在合并。 我们求出两个最小距离,但是没有考虑一个点在左边,一个点在右边的情况。  ...先求出两个最小距离中较小的一个,记为mdis   根据mid为分界【mid-mdis,mid+mdis】的闭区间筛选出可能取得最小距离的,因为平面上的还包含纵坐标,所以水平 距离不在这个范围内不可能是最短距离...同理再进入暂时数组(记为temp)的按纵坐标分类,再次筛选,并不断更新mdis 的值。

    64010

    每周算法练习——最近问题

    一、最近问题的解释     看到算法书上有最近的问题,简单来讲最近问题要求出一个包含 ? 个的集合中距离最近的两个。...二、最近问题的蛮力解法     蛮力法是最直接的方法,就是求解任意两个之间的距离,返回坐标和最小的距离 Java代码实现 package org.algorithm.closestpair; /*...三、最近问题的分治解法     分治的思想是将一个问题划分成几个独立的子问题,分别对子问题的求解,最终将子问题的解组合成原始问题的解。...如何将原始问题划分成子问题成为分治的关键。     在最近问题中,首先通过一维坐标将整个空间分成坐标点个数相同的两个区间,如下图: ?...,此时,取中间的部分,因为在我们将坐标点分开的过程中,中间的可能距离比区域 ? 和 ? 上的最小值还要小, ? 。最终返回所有可能解的最小值。

    1.3K40

    每周算法练习——最近问题

    一、最近问题的解释     看到算法书上有最近的问题,简单来讲最近问题要求出一个包含 个的集合中距离最近的两个。抽象出来就是求解任意两个之间的距离,返回距离最小的的坐标,以及最小距离。...二、最近问题的蛮力解法     蛮力法是最直接的方法,就是求解任意两个之间的距离,返回坐标和最小的距离 Java代码实现 package org.algorithm.closestpair; /*...i < length; i++) { System.out.println(i + "\t" + p[i].getX() + "\t" + p[i].getY()); } // 计算出最近...double result[] = Util.closestPair(p, length); System.out.println("最近为:"); System.out.println...((int) result[0] + "\t" + (int) result[1] + "\t" + Math.sqrt(result[2])); } } 最终的结果 三、最近问题的分治解法

    1.1K60

    算法分治

    分治 分治是一种将大问题分解成相同任务的小问题的方法,常见的分治思想之一就是归并排序(mergeSort) 归并排序 归并排序在之前的排序章节中有讲解过,这里再回顾一下: 给定一个无序列表: 从中间将其分为左右两个子列表...示例 1: 输入:[3,2,3] 输出:3 示例 2: 输入:[2,2,1,1,1,2,2] 输出:2 进阶: 尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。...分治法:如果数 a 是数组 nums 的众数,如果我们将 nums 分成两部分,那么 a 必定是至少一部分的众数。...经典的分治算法递归求解,直到所有的子问题都是长度为 1 的数组。长度为 1 的子数组中唯一的数显然是众数,直接返回即可。如果回溯后某区间的长度大于 1,我们必须将左右子区间的值合并。...代码实现: 分治法: python实现 class Solution: def majorityElement(self, nums: List[int]) -> int: def

    1K30

    分治算法

    概述 在计算机科学中,分治法是一种很重要的算法。...这种算法设计策略叫做分治法。 如果原问题可分割成k个子问题,1<k≤n,且这些子问题都可解并可利用这些子问题的解求出原问题的解,那么这种分治法就是可行的。...分治与递归像一孪生兄弟,经常同时应用在算法设计之中,并由此产生许多高效算法。...算法举例 回文 这里的回文是指资格字符串,它从头到尾读与从尾到头读的内容是一致的,比如说doggod,无论从左到右耗时从右到左都是一样的。...(3)Strassen矩阵乘法 (4)棋盘覆盖 (5)合并排序 (6)快速排序 (7)线性时间选择 (8)最接近问题 (9)循环赛日程表 (10)汉诺塔 master theorem

    64210

    分治算法

    两个数组的中位数,实际转换为分治求两个数组第k小的问题 // 分治思想 // 中位数实际就是第K小问题,当奇数时是中间数,当偶数是中间两数除以2 public double findMedianSortedArrays...,使用分治的方法进行计算局部最大和 public int maxSubArray(int[] nums){ if (nums == null || nums.length ==...count --; } } } return majorNum; } // 使用分治算法...// 使用快排思想分治分治算法 public int findKthLargest(int[] nums, int k){ // 快排找寻的是下标 return...这是统计右边放入的个数,就是右边放入个数 创建临时数组,创建索引数组,创建统计数组,初始化索引数组 归并分割,l == r 进行回溯,分为两部分 l mid,mid +1 r 治,合并统计 复制索引数组,然后索引数组进行排序

    72110

    算法分治-归并

    归并 找一个中间,把左边排好序,右边排好序,那么整体就有序。...而左边排序又是找一个中间,把左边排好序,直到这个左边就行一个值,那么就返回,左边和右边排好,再把这两个有序数组合并,再向上返回,直到整个数组都有序。 1. 912....先选择中间划分区间,把左右区间排序。排好之后,再合并两个有序数组,就可以了,用递归来实现将所有元素进行排序。...选择中间划分区间 int mid = (left + right) /2; // [left, mid] [mid + 1, right] // 2....二、算法原理 可以把这个数组划分为两个部分,找出左边部分的逆序a,再找出右边的逆序b,然后一左一右又挑出来一个逆序c,总的就是a+b+c。

    7910

    分治算法概念

    分治算法的设计思想是,将一个难以直接诶解决的大问题,分割成一些规模较小的相同的问题,以便各个击破,分而治之。  ...这种算法设计策略就是分治算法,简称分治法。   如果原问题可以分割成k个子问题,1<k<=n,且这些子问题都可解,并可利用这些子问题的解求出原问题的解,那么这种分治法就是可行的。...由分治法产生的子问题往往是原问题的较小模式,这就为使用递归技术提供了方便。在这种情况下,反复利用分治手段,可以使子问题与原问题类型一致而其规模却不断缩小,最终使子问题缩小到很容易直接求出其解。  ...分治法基本步骤: 1)把一个大问题分成多个小问题     2)分别解决每个小问题     3)把每个小问题的解组合起来。   ...分治算法应用广泛,例如排序算法(归并排序,快速排序),树分治分治,边分治),快速傅里叶变换, Strassen矩阵乘法等 题目推荐:个人分类

    55220

    算法基础:分治

    很多高效率的算法都是以分治法作为其基础思想,例如排序算法中的快速排序和归并排序。 算法思想 当需要采用分治法时,一般原问题都需要具备以下几个特征。...如果子问题之间不独立,则分治法需要重复地解决公共的子问题,造成效率低下的结果。 分治与递归的对比:分治可以采用递归或递推来分解问题。...如果分治法使用递归,那么分治法在每轮递归上,都包含了分解问题、解决问题和合并结果这 3 个步骤。 案例 二分查找 通常二分查找需要一个前提,那就是输入的数列是有序的。...二分查找的复杂度进行分析。二分查找的最差情况是,不断查找到最后 1 个数字才完成判断,那么此时需要的最大的复杂度就是 O(logn)。...因此,当你在一个有序数据环境中处理问题时,可以考虑分治法。相反,如果原问题中的数据并不是有序的,则使用分治法的可能性就会很低了。 分治法经常会用在海量数据处理中。这也是它显著区别于遍历查找方法的优势。

    46220

    《python算法教程》Day10 - 平面最近问题平面最小点问题介绍代码演示

    今天是《python算法教程》的第10篇读书笔记。笔记的主要内容是使用python实现求最小点的时间复杂度为O(nlogn)的算法。...平面最小点问题介绍 在几何学中,有一个基本问题:在一个平面的n个点中,求距离最近的两个。 最直接的思路是遍历所有的,通过比较所有点的距离找出距离最近的两,即暴力算法。...显然,这种算法的时间复杂度是不能接受的。 因此,是否可以考虑通过分治法的思路,将上述问题的解法的时间复杂度控制在O(nlog2n)?答案是可以的。...具体的算法讲解可参考下述博文: https://blog.csdn.net/lishuhuakai/article/details/9133961 但运用分治法求解上述问题时,需要注意一,距离最小的两个可能不在于同一个分组的集中...#求出平面中距离最近(若存在多,仅需求出一) import random import math #计算两的距离 def calDis(seq): dis=math.sqrt((

    2.9K120
    领券