算法-分治

算法设计

Posted by MetaNetworks on October 24, 2019
本页面总访问量

例1:填格子

有一个填充了一个格子的棋盘,用3个连续的形状卡填充

  1. 填一个形状卡,使得能把1个这样的棋盘,划分为4个这样的小棋盘
  2. 递归填充

例2:求出数组中第n小的数字

如果数组中有重复元素还需要去重一次,记录重复次数

  1. 随机选取一个数n,划分为3个部分,一个部分比n小,一个部分比n大
  2. 判断第n小的数在哪一部分
  3. 分析数组中第n小的数字等效于求那一部分第几小的数
  4. 递归