这是一个经典的分治法，给出O（n log n）

分为两个子集A1和A2，…，并显示T（n）为O（n log
n）。如果A具有多数元素v，则v也必须是A1或A2或两者的多数元素。等效的对立重述是立即进行的：（如果v分别小于等于一半，则小于等于总数的一半。）如果两个部分具有相同的多数元素，则自动成为A的多数元素。该部分具有多数元素，请计算该元素在两个部分中的重复次数（以O（n）时间），以查看其是否为多数元素。如果两个部分都占多数，则可能需要对两个候选者中的每个进行此计数，仍为O（n）。可以递归完成此拆分。基本情况是当n
= 1时。递归关系为T（n）= 2T（n / 2）+ O（n），所以根据主定理，T（n）为O（n log n）。

http://anh.cs.luc.edu/363/handouts/MajorityProblem.pdf