The majority element is the element that occurs more than half of the size of the array . 这意味着多数元素的出现超过了所有其他元素的组合 . 也就是说，如果计算多数元素出现的次数，并减去所有其他元素的出现次数，您将得到一个正数 .
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <iterator>
using namespace std;
vector <int> majorityTwoElement(vector <int> nums) {
// declare variables
multimap <int, int> nums_map;
vector <int> ret_vec, nums_unique (nums);
int count = 0;
bool debug = false;
try {
// get vector of unique numbers and sort them
sort(nums_unique.begin(), nums_unique.end());
nums_unique.erase(unique(nums_unique.begin(), nums_unique.end()), nums_unique.end());
// create map of numbers and their count
for(size_t i = 0; i < nums_unique.size(); i++){
// get number
int num = nums_unique.at(i);
if (debug) {
cout << "num = " << num << endl;
}
// get count of number
count = 0; // reset count
for(size_t j = 0; j < nums.size(); j++) {
if (num == nums.at(j)) {
count++;
}
}
// insert number and their count into map (sorted in ascending order by default)
if (debug) {
cout << "num = " << num << "; count = " << count << endl;
}
nums_map.insert(pair<int, int> (count, num));
}
// print map
if (debug) {
for (const auto &p : nums_map) {
cout << "nums_map[" << p.first << "] = " << p.second << endl;
}
}
// create return vector
if (!nums_map.empty()) {
// get data
auto it = prev(nums_map.end(), 1);
auto it1 = prev(nums_map.end(), 2);
int last_key = it->first;
int second_last_key = it1->first;
// handle data
if (last_key == second_last_key) { // tie for repeat count
ret_vec.push_back(it->second);
ret_vec.push_back(it1->second);
} else { // no tie
ret_vec.push_back(it->second);
}
}
} catch(const std::exception& e) {
cerr << "e.what() = " << e.what() << endl;
throw -1;
}
return ret_vec;
}
int main() {
vector <int> nums = {2, 1, 2, 3, 4, 2, 1, 2, 2};
try {
// get vector
vector <int> result = majorityTwoElement(nums);
// print vector
for(size_t i = 0; i < result.size(); i++) {
cout << "result.at(" << i << ") = " << result.at(i) << endl;
}
} catch(int error) {
cerr << "error = " << error << endl;
return -1;
}
return 0;
}
// g++ test.cpp
// ./a.out
0
In Monte-Carlo algorithm,
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)
}
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));
}
}
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();
}
}
0
// 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;
}
17 回答
如果允许您创建哈希表并假设哈希条目查找是常量，则只需针对出现次数对每个条目进行hash_map .
您可以通过表格进行第二次传递，获得具有最高计数的那个，但如果您事先知道表格中的元素数量，当我们点击时，您将立即知道第一遍中是否有多数元素需要指望元素 .
当然，您无法保证甚至连续出现2个元素的序列，例如1010101010101010101没有连续的1，但它是多数元素 .
我们没有被告知任何关于元素类型是否有任何排序的事情，尽管显然我们必须能够比较两个是否相等 .
随机抽样方法怎么样？您可以对sqrt（n）元素进行采样，对于发生超过sqrt（n）/ 4次的每个元素（可以在O（n）时间和O（sqrt（n））空间中天真地完成），您可以检查是否是O（n）时间的多数元素 .
该方法以高概率找到多数，因为多数元素在期望中至少采样sqrt（n）/ 2次，标准偏差最多为n ^ {1/4} / 2 .
另一种类似于我在其中一个重复链接中看到的方法的采样方法是绘制两个样本，如果它们相等，则验证您在O（n）时间内找到了多数元素 . 额外的验证步骤是必要的，因为除了大多数之外的其他元素可能不是不同的 .
对给定数组进行排序：O（nlogn） .
如果数组大小为7，则多数元素在数组中至少发生上限（7/2）= 4次 .
在对数组进行排序之后，这意味着如果首先在位置i处找到多数元素，则还在位置i floor（7/2）处找到它（4次出现） .
示例 - 给定数组A - {7,3,2,3,3,6,3}
排序数组 - {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） .
时间：O（N）
空间：O（N）
遍历树并计算哈希表中元素的出现次数 .
时间：O（n lg n）或O（n * m）（取决于使用的种类）
空间：（1）
对数组进行排序，然后计算元素的出现次数 .
采访正确答案：摩尔的投票算法
时间：O（n）
空间：O（1）
走列表比较当前数字与当前最佳猜测数字 . 如果数字等于当前最佳猜测数增加一个计数器，否则递减计数器，如果计数器达到零，则用当前数字替换当前最佳猜测数，并将计数器设置为1.当你到达结束时最佳猜测是候选人号码，再次列出候选人的实例 . 如果最终计数大于n / 2，那么它是大多数，否则没有一个 .
Majority Element:
大小为n的数组A []中的多数元素是一个出现超过n / 2次的元素（因此最多只有一个这样的元素） .
Finding a Candidate:
在O（n）中工作的第一阶段算法称为摩尔投票算法 . 算法的基本思想是，如果我们用e的所有其他元素抵消元素e的每次出现，那么如果它是多数元素则e将存在直到结束 .
上面的算法循环遍历每个元素并保持[maj_index]的计数，如果下一个元素相同则增加计数，如果下一个元素不相同则减少计数，如果计数达到0则将maj_index更改为当前element和sets count为1. First Phase算法为我们提供了候选元素 . 在第二阶段，我们需要检查候选人是否真的是多数元素 .
Second phase 很简单，可以在O（n）中轻松完成 . 我们只需要检查候选元素的数量是否大于n / 2 .
阅读geeksforgeeks了解更多详情
}
这将帮助您，如果两个元素重复相同的次数，如果不显示 .
令人遗憾的是，在5年内没有人为这个问题写过正确的解释 .
这是流式算法中的标准问题（您有一个巨大的（可能是无限的）数据流），您必须从此流计算一些统计信息，并通过此流一次 .
显然，您可以使用散列或排序来处理它，但可能是无限的流你可以清楚地耗尽内存 . 所以你必须在这里做一些聪明的事情 .
The majority element is the element that occurs more than half of the size of the array . 这意味着多数元素的出现超过了所有其他元素的组合 . 也就是说，如果计算多数元素出现的次数，并减去所有其他元素的出现次数，您将得到一个正数 .
因此，如果计算某个元素的出现次数，并减去所有其他元素的出现次数并得到数字0 - 则原始元素不能是多数元素 . 这是正确算法的基础：
声明两个变量counter和possible_element . 迭代流，如果计数器为0 - 你覆盖可能的元素并初始化计数器，如果数字与可能的元素相同 - 增加计数器，否则减少它 . Python代码：
很明显，在
O(n)（如3）之前，算法是O(n)，具有非常小的常数 . 它看起来像空间复杂度O(1)，因为我们只有三个变量初始化 . 问题是这些变量之一是一个可能长到n的计数器（当数组由相同的数字组成时） . 并存储数字n，你需要O(log (n))空间 . 所以 from theoretical point of view 是O(n)时间和O(log(n))空间 . From practical ，你可以在longint中拟合2 ^ 128个数字，这个数组中的元素数量是难以想象的巨大 .另请注意，该算法仅在存在多数元素时才有效 . 如果这样的元素不存在，它仍然会返回一些数字，这肯定是错误的 . （很容易修改算法来判断多数元素是否存在）
历史 Channels ：这个算法是1982年由Boore，Moore在某处发明的，名为Boyer–Moore majority vote algorithm
这就是我在C中使用矢量和多图（带有重复键的JSON）的方法 .
In Monte-Carlo algorithm,
Time Complexity O(n)
//假设我们得到一个数组A. //如果我们在给定数组中有所有元素，这样每个元素都小于K，那么我们就可以创建一个长度为K 1的附加数组B.
//使用0初始化数组的每个索引处的值.//然后遍历给定的数组A，对于每个数组值A [i]，在创建的数组中的相应索引A [i]处将值递增1 B.
//在迭代数组A之后，现在遍历数组B并找到最大值 . 如果您发现值大于n / 2，则返回该特定索引 .
//如果K <= n则等于O（n），时间复杂度将为O（n K） .
//我们在这里有一个约束，即数组的所有元素都是O（K） . //假设每个元素小于或等于100，在这种情况下K为100 .
感谢以前的答案，这让我知道Bob Boyer's algo. :)
Java通用版本：Boyer算法的修改版本
注意：基本类型的数组可以使用包装器 .
}
修改版Boyer的算法，
3通过哪里，
在第一遍中，我们对数组进行了前向迭代
在第二遍中，我们对数组进行反向迭代 .
在第三遍中，获取在第一遍和第二遍中获得的多数元素的计数 .
技术上是线性复杂度算法（O（3n）） . 我相信这应该适用于一个多数元素至少发生n / 2次的数组 .
Code tested here
多数元素（如果存在）也将是中位数 . 我们可以在O（n）中找到中位数，然后检查它确实是O（n）中的有效多数元素 . 更多实施细节link
要查找数组中的大部分元素，您可以使用摩尔的多数投票算法，这是最好的算法之一 .
Time Complexity:
O(n) or linear timeSpace Complexity:
O(1) or constant space阅读更多Moore's Majority Vote Algorithm和GeeksforGeeks