题目：求众数
给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在众数。
示例 1:
输入: [3,2,3]
输出: 3
示例 2:
输入: [2,2,1,1,1,2,2]
输出: 2
首先了解一下什么是分治
*：
在计算机科学中，分治法是建基于多项分支递归的一种很重要的算法范式。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
这个技巧是很多高效算法的基础，如排序算法（快速排序、归并排序）、傅立叶变换（快速傅立叶变换）。
另一方面，理解及设计分治法算法的能力需要一定时间去掌握。正如以归纳法去证明一个理论，为了使递归能够推行，很多时候需要用一个较为概括或复杂的问题去取代原有问题。而且并没有一个系统性的方法去适当地概括问题。
分治法这个名称有时亦会用于将问题简化为只有一个细问题的算法，例如用于在已排序的列中查找其中一项的折半搜索算法（或是在数值分析中类似的勘根算法）。这些算法比一般的分治算法更能有效地运行。其中，假如算法使用尾部递归的话，便能转换成简单的循环。但在这广义之下，所有使用递归或循环的算法均被视作“分治算法”。因此，有些作者考虑“分治法”这个名称应只用于每个有最少两个子问题的算法。而只有一个子问题的曾被建议使用减治法这个名称。
分治算法通常以数学归纳法来验证。而它的计算成本则多数以解递归关系式来判定。
- 第一种
集合（Map），实现。执行用时：46 ms
public int majorityElement(int[] nums) {
// [n/2] 元素
int majorityElement = nums.length / 2;
// 创建一个集合
Map<Integer, Integer> map = new HashMap();
for (int num : nums) {
// 思路：数组元素为key，出现次数为value。如果存在key，value+1,如果不存在key，第一次设置value 为1
map.put(num, map.get(num) != null ? map.get(num).intValue() + 1 : 1);
}
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
// 出现次数和[n/2] 进行比较，大于，则返回（其实应该用一个集合来保存所有满足条件的众数，然后再返回）
if (entry.getValue() > majorityElement) {
return entry.getKey();
}
}
return 0;
}
- 第二种
分治法 实现
// 用分治法求众数 #include <iostream>
#include <cstdio> using namespace std; // 本程序的关键。 以中间的数字为界限。 确定左右起始和终止界限
void split(int s[], int n, int &l, int &r)
{
int mid = n/2;
for(l=0; l<n; ++l)
{
if (s[l] == s[mid])
break;
}
for(r=l+1; r<n; ++r)
{
if (s[r] != s[mid])
break;
} } // num 众数。 maxCnt 重数
void getMaxCnt(int &mid, int &maxCnt, int s[], int n)
{
int l, r;
split(s, n, l, r); // 进行分割。这个函数是本程序的关键
int num = n/2;
int cnt = r-l; // update
if (cnt > maxCnt)
{
maxCnt = cnt;
mid = s[num];
} // l 表示左边的个数。左边的个数必须大于 maxCnt 才有必要搜寻
if (l+1 > maxCnt)
{
getMaxCnt(mid, maxCnt, s, l+1);
} // 右边搜寻, 右边数组的起始地址要变更
if (n-r > maxCnt)
{
getMaxCnt(mid, maxCnt, s+r, n-r);
}
} int main(void)
{
int s[] = {1, 2, 2, 2, 3, 3, 5, 6, 6, 6, 6};
int n = sizeof(s)/sizeof(s[0]); int maxCnt = 0;
int num = 0;
getMaxCnt(num, maxCnt, s, n);
printf("%d %d\n", num, maxCnt); return 0;
}
- 第三种
时间最快的 执行用时：7 ms
public int majorityElement2(int[] nums) {
int result = nums[0], count = 0;
for (int i = 0; i < nums.length; i++) {
if (count == 0) {
result = nums[i];
count++;
} else if (result == nums[i]) {
count++;
} else {
count--;
}
}
return result;
}