题目：给定一个大小为 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; }
原文：https://www.cnblogs.com/kingxiaozi/p/10546804.html