分治算法
概念
分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。即一种分目标完成程序算法，简单问题可用二分法完成。
步骤
- 分解，将要解决的问题划分成若干规模较小的同类问题；
- 求解，当子问题划分得足够小时，用较简单的方法解决；
- 合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。
应用场景
运用分治策略解决的问题一般来说具有以下特点：
原问题可以分解为多个子问题
这些子问题与原问题相比，只是问题的规模有所降低，其结构和求解方法与原问题相同或相似。原问题在分解过程中，递归地求解子问题
由于递归都必须有一个终止条件，因此，当分解后的子问题规模足够小时，应能够直接求解。在求解并得到各个子问题的解后
应能够采用某种方式、方法合并或构造出原问题的解。
不难发现，在分治策略中，由于子问题与原问题在结构和解法上的相似性，用分治方法解决的问题，大都采用了递归的形式。在各种排序方法中，如归并排序、堆排序、快速排序等，都存在有分治的思想。
应用案例
求众数
给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在众数。
示例 1:
输入: [3,2,3]
输出: 3
示例 2:
输入: [2,2,1,1,1,2,2]
输出: 2
想法
如果我们知道数组左边一半和右边一半的众数，我们就可以用线性时间知道全局的众数是哪个。
算法
这里我们使用经典的分治算法递归求解，直到所有的子问题都是长度为 1 的数组。由于传输子数组需要额外的时间和空间，所以我们实际上只传输子区间的左右指针 lo 和 hi 表示相应区间的左右下标。长度为 1 的子数组中唯一的数显然是众数，直接返回即可。如果回溯后某区间的长度大于 1 ，我们必须将左右子区间的值合并。如果它们的众数相同，那么显然这一段区间的众数是它们相同的值。否则，我们需要比较两个众数在整个区间内出现的次数来决定该区间的众数。原问题的答案就是下标为 00 和 nn 之间的众数这一子问题。
/**
* @param {number[]} nums
* @return {number}
*/
var majorityElement = function(nums) {
let countRange=(num,left,right)=>{
let count=0;
for(let i=left;i<=right;i++){
if(nums[i]==num){
count++
}
}
return count
}
let majority=(le,ri)=>{
if(le==ri){
return nums[le]
}
let mid=Math.floor((ri-le)/2) +le;
let left=majority(le,mid);
let right=majority(mid+1,ri);
if(left==right){
return left
}
let leftCount=countRange(left,le,ri);
let rightCount=countRange(right,le,ri);
return leftCount>rightCount?left:right;
}
return majority(0,nums.length-1)
}