江苏龙网

  1. 主页 > 生活百科 > >

一文搞懂分治算法( 三 )

分治算法


  • 完全在中间的左侧
  • 完全在中间的右侧
  • 包含中间左右两个节点的一个序列
用一张图可以表示为：
一文搞懂分治算法

文章插图
 
所以在具体考虑的时候需要将无法递归得到结果的中间那个最大值串的结果也算出来参与左侧、右侧值得比较 。
力扣53. 最大子序和在实现的代码为：
public int maxSubArray(int[] nums) {    int max=maxsub(nums,0,nums.length-1);    return max;}int maxsub(int nums[],int left,int right){    if(left==right)        return  nums[left];    int mid=(left+right)/2;    int leftmax=maxsub(nums,left,mid);//左侧最大    int rightmax=maxsub(nums,mid+1,right);//右侧最大    int midleft=nums[mid];//中间往左    int midright=nums[mid+1];//中间往右    int team=0;    for(int i=mid;i>=left;i--)    {        team+=nums[i];        if(team>midleft)            midleft=team;    }    team=0;    for(int i=mid+1;i<=right;i++)    {        team+=nums[i];        if(team>midright)            midright=team;    }    int max=midleft+midright;//中间的最大值    if(max<leftmax)        max=leftmax;    if(max<rightmax)        max=rightmax;    return  max;}最近点对最近点对是一个分治非常成功的运用之一 。在二维坐标轴上有若干个点坐标 ， 让你求出最近的两个点的距离 ， 如果让你直接求那么枚举暴力是个非常非常大的计算量,我们通常采用分治的方法来优化这种问题 。
一文搞懂分治算法

文章插图
 
如果直接分成两部分分治计算你肯定会发现如果最短的如果一个在左一个在右会出现问题 。我们可以优化一下 。
在具体的优化方案上 ， 按照x或者y的维度进行考虑 ， 将数据分成两个区域 ， 先分别计算(按照同方法)左右区域内最短的点对 。然后根据这个两个中较短的距离向左和向右覆盖 ， 计算被覆盖的左右点之间的距离 ， 找到最小那个距离与当前最短距离比较即可 。
一文搞懂分治算法

文章插图
 
这样你就可以发现就这个一次的操作(不考虑的情况) ， 左侧红点就避免和右侧大部分红点进行距离计算(O(n2)的时间复杂度) 。事实上 ， 在进行左右区间内部计算的时候 ， 它其实也这样递归的进行很多次分治计算 。如图所示：
一文搞懂分治算法

文章插图
 
这样下去就可以节省很多次的计算量 。
但是这种分治会存在一种问题就是二维坐标可能点都聚集某个方法某条轴那么可能效果并不明显(点都在x=2附近对x分割作用就不大) ， 需要注意一下 。
杭电1007推荐给大家 ， ac的代码为：
import JAVA.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.io.OutputStreamWriter;import java.io.PrintWriter;import java.io.StreamTokenizer;import java.util.ArrayList;import java.util.Arrays;import java.util.Comparator;import java.util.List;public class Main {    static int n;    public static void main(String[] args) throws IOException {        StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));        //List<node>list=new ArrayList();         while(in.nextToken()!=StreamTokenizer.TT_EOF)         {             n=(int)in.nval;if(n==0) {break;}            node no[]=new node[n];                         for(int i=0;i<n;i++)             {                 in.nextToken();double x=in.nval;                 in.nextToken();double y=in.nval;                // list.add(new node(x,y));                 no[i]=new node(x,y);             }             Arrays.sort(no, com);            double min= search(no,0,n-1);            out.println(String.format("%.2f", Math.sqrt(min)/2));out.flush();         }             }    private static double search(node[] no, int left,int right) {        int mid=(right+left)/2;        double minleng=0;        if(left==right) {return Double.MAX_VALUE;}        else if(left+1==right) {minleng= (no[left].x-no[right].x)*(no[left].x-no[right].x)+(no[left].y-no[right].y)*(no[left].y-no[right].y);}        else minleng= min(search(no,left,mid),search(no,mid,right));        int ll=mid;int rr=mid+1;        while(no[mid].y-no[ll].y<=Math.sqrt(minleng)/2&&ll-1>=left) {ll--;}        while(no[rr].y-no[mid].y<=Math.sqrt(minleng)/2&&rr+1<=right) {rr++;}        for(int i=ll;i<rr;i++)        {            for(int j=i+1;j<rr+1;j++)            {                double team=0;                if(Math.abs((no[i].x-no[j].x)*(no[i].x-no[j].x))>minleng) {continue;}                else                {                     team=(no[i].x-no[j].x)*(no[i].x-no[j].x)+(no[i].y-no[j].y)*(no[i].y-no[j].y);                    if(team<minleng)minleng=team;                }            }        }        return minleng;        }    private static double min(double a, double b) {        // TODO 自动生成的方法存根        return a<b?a:b;    }    static Comparator<node>com=new Comparator<node>() {        @Override        public int compare(node a1, node a2) {            // TODO 自动生成的方法存根            return a1.y-a2.y>0?1:-1;        }};    static class node    {        double x;        double y;        public node(double x,double y)        {            this.x=x;            this.y=y;        }    }}


推荐阅读


上一篇：邦崴古树茶特点,饱满厚重邦崴味

下一篇：安神茶有哪些呢,七叶胆茶功效有哪些