find数组中的多数元素
大多数元素是发生超过数组大小的一半的元素。
如何在O(n)find数组中的多数元素？
示例input：
{2,1,2,3,4,2,1,2,2}
预期产出：
2
多数元素（如果存在的话）也是中位数。 我们可以在O（n）中find中位数，然后检查它是否是O（n）中的有效多数元素。 更多细节实现链接
// returns -1 if there is no element that is the majority element, otherwise that element // funda :: if there is a majority element in an array, say x, then it is okay to discard // a part of that array that has no majority element, the remaining array will still have // x as the majority element // worst case complexity : O(n) int findMajorityElement(int* arr, int size) { int count = 0, i, majorityElement; for (i = 0; i < size; i++) { if (count == 0) majorityElement = arr[i]; if (arr[i] == majorityElement) count++; else count--; } count = 0; for (i = 0; i < size; i++) if (arr[i] == majorityElement) count++; if (count > size/2) return majorityElement; return -1; }
很遗憾，5年来没有人为这个问题写过正确的解释。
这是streamalgorithm中的一个标准问题（您有一个巨大的（可能是无限的）数据stream），您必须从这个stream中计算一些统计数据，并通过这个数据stream一次。
很明显，你可以用散列或sorting来处理它，但是如果有潜在的无限stream，你显然会耗尽内存。 所以你必须在这里做一些聪明的事情。
大多数元素是发生超过数组大小的一半的元素 。 这意味着多数元素出现的次数多于所有其他元素的总和，或者如果您计算次数，多数元素出现，减去所有其他元素的数量，您将得到一个正数。
所以如果你计算一些元素的数量，并减去所有其他元素的数量，并得到数字0 – 那么你的原始元素不能是多数元素。 这个如果有一个正确的algorithm的基础：
有两个variables，计数器和可能的元素。 迭代stream，如果计数器是0 – 你覆盖可能的元素和初始化计数器，如果数字是相同的可能元素 – 增加计数器，否则减less它。 Python代码：
def majority_element(arr): counter, possible_element = 0, None for i in arr: if counter == 0: possible_element, counter = i, 1 elif i == possible_element: counter += 1 else: counter -= 1 return possible_element
很明显，在O(n) （如3）之前，algorithm是O(n) ，其常数非常小。 另外看起来空间复杂度是O(1) ，因为我们只有三个variables被初始化。 问题是这些variables之一是一个计数器，它可能会长到n （当数组由相同的数字组成时）。 为了存储数字n你需要O(log (n))空间。 所以从理论的angular度来看，它是O(n)时间和O(log(n))空间。 从实际的angular度来看 ，你可以在longint中放入2 ^ 128的数字，这个数组中的元素数目是无法想象的巨大。
还要注意，algorithm只有在有多数元素时才起作用。 如果这样的元素不存在，它仍然会返回一些数字，这肯定是错误的。 （很容易修改algorithm来判断是否存在多数元素）
历史通道：这个algorithm是由Boyer，Moore于1982年在某处发明的，称为Boyer-Moore多数票algorithm
多数元素：
大小为n的数组A []中的多数元素是出现超过n / 2次（因此最多只有一个这样的元素）的元素。
寻找候选人：
在O（n）中工作的第一阶段algorithm被称为Moore的投票algorithm。 该algorithm的基本思想是，如果我们用与e不同的所有其他元素来消除每个元素e的出现，那么如果它是多数元素，则e将存在直到结束。
findCandidate(a[], size) 1. Initialize index and count of majority element maj_index = 0, count = 1 2. Loop for i = 1 to size – 1 (a)If a[maj_index] == a[i] count++ (b)Else count--; (c)If count == 0 maj_index = i; count = 1 3. Return a[maj_index]
以上algorithm循环遍历每个元素，并维护一个[maj_index]的计数，如果下一个元素相同，则增加计数，如果下一个元素不相同，则递减计数，并且如果计数达到0，则将maj_index更改为当前元素并将计数设置为1. First Phasealgorithm给了我们一个候选元素。 在第二阶段，我们需要检查候选人是否真的是多数人。
第二阶段很简单，可以很容易地在O（n）中完成。 我们只需要检查候选元素的计数是否大于n / 2。
阅读geeksforgeeks的更多细节
时间：O（N）
空间：O（N）
走树并计算哈希表中元素的出现次数。
时间：O（n lg n）或O（n * m）（取决于所使用的sorting）
空间：（1）
对数组进行sorting，然后统计元素的出现次数。
面试正确答案：摩尔的投票algorithm
时间：O（n）
空间：O（1）
步行列表比较当前数字与当前最佳猜测数字。 如果数字等于当前最佳猜测数字，则递增计数器，否则递减计数器，如果计数器达到零，则用当前数字replace当前最佳猜测数字，并将计数器设置为1.当您到达最后时，当前最好的猜测就是候选人数字，再次列出候选人的实例。 如果最终计数大于n / 2，那么它是大多数，否则就没有一个。
随机抽样方法如何？ 你可以对sqrt（n）元素进行取样，对于每个发生sqrt（n）/ 4次以上的元素（可以在O（n）时间和O（sqrt（n））空间中天真地完成），你可以检查无论是在O（n）时间的多数元素。
由于多数元素在预期中至less被sqrt（n）/ 2次采样，标准偏差最多为n ^ {1/4} / 2，所以这种方法find了大部分。
另一种与我在其中一个重复链接中看到的方法相似的抽样方法是绘制两个样本，如果相等，则validation您是否在O（n）时间内find了大多数元素。 额外的validation步骤是必要的，因为除了大多数以外的其他元素可能并不明显。
在Monte-Carloalgorithm中，
Majority (a,n) //a[]-array of 'n' natural numbers { j=random(0,1,....,n-1) /*Selecting the integers at random ranging from 0 to n-1*/ b=a[j];c=0; for k from 0 to n-1 do { if a[k]=b then, c=c+1; } return (c>n/2) }
要find数组中的大部分元素，可以使用Moore的多数投票algorithm，它是最好的algorithm之一。
时间复杂度： O(n) or linear time
空间复杂性： O(1) or constant space
请阅读Moore的多数投票algorithm和GeeksforGeeks
如果您可以创build一个散列表，并假设散列条目查找是恒定的，那么您只需对发生次数的每个条目进行hash_map。
你可以在桌子上进行第二次传球，但是如果你事先知道表格中的元素数量，那么当我们击中在元素上需要计数。
当然，你甚至不能保证甚至连续出现2个元素，例如1010101010101010101没有连续的1，但它是多数元素。
我们没有告诉任何关于元素types是否有任何sorting的情况，但显然我们必须能够比较两者之间的平等。
int majorityElement(int[] num) { int major=num[0], count = 1; for(int i=1; i<num.length;i++){ if(count==0){ count++; major=num[i]; } else if(major==num[i]){ count++; } else count--; } return major; }
时间复杂度O（n）
public class MajorityElement { public static void main(String[] args) { int arr[]={3,4,3,5,3,90,3,3}; for(int i=0;i<arr.length;i++) { int count=0; int j=0; while(j<arr.length-1) { if(i==j) j=j+1; if(arr[i]==arr[j]) count++; j++; } if(count>=arr.length/2) { System.out.println("majority element"+arr[i]); break; } } }
}
一个修改版Boyer的algorithm，
- 3路过的地方，
- 在第一遍中，我们进行数组的前向迭代
- 在第二遍中，我们做了一个数组的反向迭代。
- 在第三遍中，获得在第一遍和第二遍中获得的多数元素。
从技术上来说，线性复杂度algorithm（O（3n））。 我相信这应该适用于具有至lessn / 2次的多数元素的数组。
#include <iostream> #include <vector> template <typename DataType> DataType FindMajorityElement(std::vector<DataType> arr) { // Modified BOYERS ALGORITHM with forward and reverse passes // Count will stay positive if there is a majority element auto GetMajority = [](auto seq_begin, auto seq_end) -> DataType{ int count = 1; DataType majority = *(seq_begin); for (auto itr = seq_begin+1; itr != seq_end; ++itr) { count += (*itr == majority) ? 1 : -1; if (count <= 0) { // Flip the majority and set the count to zero whenever it falls below zero majority = *(itr); count = 0; } } return majority; }; DataType majority1 = GetMajority(arr.begin(), arr.end()); DataType majority2 = GetMajority(arr.rbegin(), arr.rend()); int maj1_count = 0, maj2_count = 0; // Check if any of the the majority elements is really the majority for (const auto& itr: arr) { maj1_count += majority1 == itr ? 1 : 0; maj2_count += majority2 == itr ? 1 : 0; } if (maj1_count >= arr.size()/2) return majority1; if (maj2_count >= arr.size()/2) return majority2; // else return -1 return -1; }
代码在这里testing
感谢以前的答案，这启发我了解鲍勃·博耶的algorithm。 🙂
Java通用版本：Boyeralgorithm的修改版本
注意：原始types的数组可以使用包装器。
import com.sun.deploy.util.ArrayUtil; import com.sun.tools.javac.util.ArrayUtils; /** * Created by yesimroy on 11/6/16. */ public class FindTheMajority { /** * * @param array * @return the value of the majority elements */ public static <E> E findTheMajority(E[] array){ E majority =null; int count =0; for(int i=0; i<array.length; i++){ if(count==0){ majority = array[i]; } if(array[i].equals(majority)){ count++; }else{ count--; } } count = 0; for(int i=0; i<array.length ; i++){ if(array[i].equals(majority)){ count++; } } if(count > (array.length /2)){ return majority; }else{ return null; } } public static void main(String[] args){ String[] test_case1 = {"Roy","Roy","Roy","Ane","Dan","Dan","Ane","Ane","Ane","Ane","Ane"}; Integer[] test_case2 = {1,3,2,3,3,3,3,4,5}; System.out.println("test_case1_result:" + findTheMajority(test_case1)); System.out.println("test case1 the number of majority element should greater than" + test_case1.length/2); System.out.println(); System.out.println("test_case2_result:" + findTheMajority(test_case2)); System.out.println("test case2 the number of majority element should greater than" + test_case2.length/2); System.out.println(); }
}
//假设我们得到一个数组A. //如果给定数组中的所有元素使得每个元素小于K，那么我们可以创build一个长度为K + 1的附加数组B.
//用0初始化数组的每个索引处的值//然后遍历给定的数组A，对于每个数组值A [i]，在创build的数组的相应索引A [i]处将值递增1 B.
//在遍历数组A之后，现在遍历数组B，并find最大值。 如果你发现大于n / 2的值，那么返回那个特定的索引。
//如果K <= n则时间复杂度为O（n + K），则等价于O（n）。
//这里我们有一个约束，即数组的所有元素都是O（K）。 //假设每个元素小于或等于100，在这种情况下K是100。
import javax.print.attribute.standard.Finishings; public class MajorityElement { private static int maxElement=100; //Will have all zero values initially private static int arrB[]=new int[maxElement+1]; static int findMajorityElement(int[] arrA) { int count = 0, i, majorityElement; int n=arrA.length; for (i = 0; i < n; i++) { arrB[arrA[i]]+=1; } int maxElementIndex=1; for (i = 2; i < arrB.length; i++){ if (arrB[i]>n/2) { maxElementIndex=i; break; } } return maxElementIndex; }` public static void main(String[] args) { int arr[]={2,6,3,2,2,3,2,2}; System.out.println(findMajorityElement(arr)); } }
对给定数组进行sorting：O（nlogn）。
如果数组大小为7，那么多数元素在arrays中至less会出现上限（7/2）= 4次。
数组sorting后，这意味着如果多数元素首先在位置ifind，它也可以在位置i + floor（7/2）（4次出现）find。
示例 – 给定数组A – {7,3,2,3,3,6,3}
sorting数组 – {2,3,3,3,3,6,7}
元素3位于位置1（数组索引从0开始）。如果位置1 + 3 =第4个元素也是3，则表示3是多数元素。
如果我们从头开始循环数组
比较位置0和位置3，不同的元素2和3.比较位置1和位置4，相同的元素。 我们发现我们的多数匹配！
复杂性 – O（n）
总时间复杂度 – O（n）。
