算法篇七 分治算法
👔

算法篇七 分治算法

Created
Jul 16, 2021 08:36 PM
Tags
算法

分治算法的思想

分治算法(divide and conquer)的核心思想其实就是四个字,分而治之 ,也就是将原问题划分成n个规模较小,并且结构与原问题相似的子问题,递归地解决这些 子问题,然后再合并其结果,就得到原问题的解。 这个定义看起来有点类似递归的定义。
关于分治和递归的区别,分治算法是一种处理问题的思想,递归是一种编程技巧。分治算法一般都比较适合用递归来实现。
分治算法的递归实现中,每一层递归都会涉及这样三个操作:
  • 分解: 将原问题分解成一系列子问题
  • 解决: 递归地求解各个子问题,若子问题足够小,则直接求解
  • 合并: 将子问题的结果合并成原问题
分治算法能解决的问题,一般需要满足下面这几个条件:
  • 原问题与分解成的小问题具有相同的模式
  • 原问题分解成的子问题可以独立求解, 子问题之间没有相关性, 这一点是分治算法跟动态规划的明显区别
  • 具有分解终止条件, 也就是说, 当问题足够小时, 可以直接求解
  • 可以将子问题合并成原问题, 而这个合并操作的复杂度不能太高

在归并排序的同时, 求原数组有多少个逆序对

public class LeetCode { public static void main(String[] args) { Merge merge = new Merge(); int[] a = new int[]{1,5,6,2,3,4}; merge.mergeStart(a); // 排序好的数组 System.out.println(Arrays.toString(a)); // 逆序对数 System.out.println(merge.num); } } class Merge { /** * 存储原始数组有多少个逆序对 */ public int num = 0; public void mergeStart(int[] a) { merge(a, 0, a.length - 1); } private void merge(int[] a, int l, int r) { // l >= r代表当前已经无法分割 if (l >= r) return; int mid = (l + r) / 2; merge(a, l, mid); merge(a, mid + 1, r); int left = l; int right = mid + 1; // 临时数组用来存储排序好的元素 int[] tmp = new int[r - l + 1]; // 临时数组下标 int k = 0; // 当左指针和右指针后面还都有元素的时候 while (left <= mid && right <= r) { if (a[left] < a[right]) { // 左指针数比右指针数小, 把左指针数放到临时数组 tmp[k++] = a[left++]; } else { tmp[k++] = a[right++]; // 否则就是逆序对, 这时候左边数组里, 左指针后面的所有元素都比a[right]要大, 所以都是逆序对 num += (mid - left + 1); } } // 处理左边剩下的数 while (left <= mid) { tmp[k++] = a[left++]; } // 处理右边剩下的数 while (right <= r) { tmp[k++] = a[right++]; } // 把排序好的数组赋值给原数组 for (int i = 0; i < tmp.length; i++) { a[l + i] = tmp[i]; } } }