分治算法 例题

分治算法主要就是考虑两个问题：
1、怎么把一个数据量比较大的问题，转换成两个数据量比较小的同类型问题，一般都采用二分法
2、怎么把两个数据量比较小的同类型问题合并成原来的数据量比较大的问题
也就是

考虑这些问题，就基本可以解决这个问题了

分治算法的基本思想：将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。即一种分目标完成程序算法，简单问题可用二分法完成。

#例题一

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1:
输入: [3,2,3]
输出: 3
示例 2:
输入: [2,2,1,1,1,2,2]
输出: 2

package nunber2;

import java.util.Scanner;
//其实就是求众数问题
//求一个数的众数，如果一个数再一列数据是众数，那他在左边和又变也都是众数
//怎么去界限一个左边和右边——从中间，也就是二分
public class Main {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int[] nums= {2,3,2};
		System.out.println(majorityElement(nums));
	}
	
	public static int majorityElement(int[] nums) {
		return solution(nums,0,nums.length-1);
	}
	public static int solution(int[] nums,int left,int right) {
		//如果当前的数据只有一个，那这个就是众数
		if(left==right) {
			return nums[left];
		}
		
		int mid=(left+right)/2;
		int leftMajority=solution(nums,left,mid);
		int rightMajority=solution(nums,mid+1,right);
		//只是告诉了左边和右边相等的情况
		if(leftMajority==rightMajority)
			return leftMajority;//如果左边和右边的众数是一样的，就可以返回了
		
		else {//左边和右边不相等的情况怎么办-统计左右两边的数量，看哪一个多，就哪一个是众数
			int leftCount=count(nums,left,mid,leftMajority);
			int rightCount=count(nums,mid+1,right,rightMajority);
			return leftCount>rightCount?leftMajority:rightMajority;
		}
	}
	public static int count(int[] nums,int left,int right,int majority) {
		int count=0;
		for (int i = left; i <=right; i++) {
			if(nums[i]==majority)
				count++;
		}
		return count;
	}
}

#例题二

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

• 这里展示的是不用分治算法的。就是简单粗暴解题，思路就是：想要得到中间i到j之间的数据，就要用j项和减去i项和

package nunber2;

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int[] nums= {-2,1,-3,4,-1,2,1,-5,4};
		System.out.println(maxSubArray(nums));
	}
//	想要得到中间i到j之间的数据，就要用j项和减去i项和
	 public static int maxSubArray(int[] nums) {
		 int res=Integer.MIN_VALUE;
		 int min=0;
		 if(nums.length==1)//如果只有一个数据，就直接返回就可以；
			 return nums[0];
		 
		 for (int i = 1; i < nums.length; i++) {
			nums[i]+=nums[i-1];
		 }
		 
		 for (int i = 0; i < nums.length; i++) {
			res=Math.max(res, nums[i]-min);
			
			min=min>nums[i]?nums[i]:min;
		}
		 return res;
		
	 }

}

• 这里展示的是错误的分治算法的代码，我个人觉得思路可行，但是败给了java对数组作为形式参数是做引用的，所以形参的数组改变，也会改变实参的数组
• 所以这里错误代码的展示的结果就是每次数组的最后一个数字，没有别的结果

package nunber2;

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int[] nums= {-2,1,-3,4,-1,2,1,-5,4};
		System.out.println(maxSubArray(nums));
	}
	//求一组数组的最大子序列和，其实就是左边子数组求最大子序列和，右边求最大子序列和，最后合并一起分析
	 public static int maxSubArray(int[] nums) {
		 //如果数组就一个数，就直接返回啦
		 if(nums.length==1)
			 return nums[0];
		 
		 int[] res=new int[3];
		 res= solution(nums,0,nums.length-1,res);
		 return res[2];
	 }
	 //找出最大子序列的对应的数
	 public static int[] solution(int[] nums,int left,int right,int res[]) {
		 if(left==right) {
			 res[0]=left;//结果的左边坐标
			 res[1]=right;//结果的右边坐标
			 res[2]=nums[left];//保存结果
			 return res;
		 }
		 
		 int mid=(left+right)/2;
		 //这里的res是可变的，是会随着res的变化而变化
		 int[] leftIndex=solution(nums,left,mid,res);
		 int[] rightIndex=solution(nums,mid+1,right,res);
		 
		 int tempRes=0;
		 for (int i = leftIndex[0]; i <= rightIndex[1]; i++) {
			tempRes+=nums[i];
		 }
		 int max=Max(leftIndex[2],rightIndex[2],tempRes);
		 
		 if(max==leftIndex[2])
			 res=leftIndex;
		 else if(max==rightIndex[2])
			 res=rightIndex;
		 else {
			 res[0]=leftIndex[0];
			 res[1]=rightIndex[1];
			 res[2]=tempRes;
		 }
		 
		 return res;
	 }
	 
	 //比较三个数的大小，返回其中最大的那个
	 public static int Max(int left,int right,int res) {
		 int max=0;
		 if(left>right)
			 max=left;
		 else
			 max=right;
		 
		 max=Math.max(max, res);
		 return max;
	 }

}

• 这里展示的就是用分治算法实现的真正算法实现，是力扣里面的题解

package nunber2;

import java.util.Scanner;
public class Status {
	//构造一个对象
	public int lSum, rSum, mSum, iSum;
//	lSum 表示 [l,r] 内以 l 为左端点的最大子段和
//	rSum 表示 [l,r] 内以 r 为右端点的最大子段和
//	mSum 表示 [l,r] 内的最大子段和
//	iSum 表示 [l,r] 的区间和

    public Status(int lSum, int rSum, int mSum, int iSum) {
        this.lSum = lSum;
        this.rSum = rSum;
        this.mSum = mSum;//结果
        this.iSum = iSum;
    }
    //主函数
    public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int[] nums= {-2,1,-3};
		System.out.println(maxSubArray(nums));
	}
    
    public static int maxSubArray(int[] nums) {
    	return getInfo(nums, 0, nums.length - 1).mSum;
    }

    public static Status getInfo(int[] a, int l, int r) {
    	if (l == r) //如果左边的坐标等于右边的左边，数组只有一个数，就可以直接返回
    		return new Status(a[l], a[l], a[l], a[l]);
	    int m = (l + r) >> 1;//右移一位，就是相当于除以2，这个在计算机组成原理里面讲的右移运算是一样的
	    Status lSub = getInfo(a, l, m);//左边的最大序列
	    Status rSub = getInfo(a, m + 1, r);//右边的最大序列
	    return pushUp(lSub, rSub);
    }
	//合并数据
	public static Status pushUp(Status l, Status r) {
	    int iSum = l.iSum + r.iSum;//总的数据和等于左边数据和＋右边的数和
	    int lSum = Math.max(l.lSum, l.iSum + r.lSum);
	    int rSum = Math.max(r.rSum, r.iSum + l.rSum);
	    int mSum = Math.max(Math.max(l.mSum, r.mSum), l.rSum + r.lSum);
	    return new Status(lSum, rSum, mSum, iSum);
	}

	
}

最后

以上就是清脆洋葱为你收集整理的分治算法 例题的全部内容，希望文章能够帮你解决分治算法 例题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。