实验一 分治法求众数
一、实验目的
掌握递归与分治方法的基本设计思想与原则,学会递归技术编程技巧。
二、实验内容
设计、编写程序,递归求解众数问题。调试、运行程序,观察、记录结果并分析
三、实验分析与实现
1. 分治法的原则是将问题一分为二,答案只可能存在于其中的一部分之中,因此可以跳过
另一部分,从而提高算法效率。
2. 经 典 分 治 法 解 决 查 找 问 题 的 方 法 是 这 样 的 : 对 于 一 个 升 序 数 组 , 一 开 始 令
left=0,right=arr.length 取其中间数 mid=(left+right)/2。当查找数 aim<arr[mid],取左边区间,令
right=mid-1,更新 mid;反之取右边区间。直到找到或者区间收束完毕结束循环。
3. 考虑这样一个问题:对于一个无序数组,参考上述算法,能不能用分治法求出众数?
以下面的数组为例:
4. 再考虑这样一个问题:能不能不排序求出众数?排序的目的是使中间数的左边和右边没
有相同的数,没有相同的数对于计算机来说,最简单的方法就是左边的所有数都小于中间数,
右边的所有数都大于中间数,这样的时间复杂度只要 O(arr.length),而对左右两边的数逐一比对,
需要 O(leftarr.length*rightarr.length)。
5. 快排的算法是取数组的第一个数或者最后一个数,设置双指针遍历整个数组,最后可以
保证这个数的左边所有数都小于这个数,这个数右边的所有数都大于这个数,正好是我们需要
的结果。
6. 所以只要用快排的算法排一次就可以了,不需要排序到底。以下是算法演示:
评论10