Элемент most - это элемент, который содержит более половины размера массива.
Как найти элемент большинства в массиве в O(n)?
Пример ввода:
{2,1,2,3,4,2,1,2,2}
Ожидаемый результат:
2
Найти элемент большинства в массиве
Ответ 1
Элемент большинства (если он существует) также будет медианой. Мы можем найти медиану в O (n) и затем проверить, что она действительно является допустимым мажоритарным элементом в O (n). Более подробная информация для реализации ссылка
Ответ 2
// 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;
}
Ответ 3
Грустно видеть, что за 5 лет никто не написал надлежащего объяснения этой проблемы.
Это стандартная проблема в алгоритмах потоковой передачи (где у вас огромный (потенциально бесконечный) поток данных), и вам нужно вычислить некоторую статистику из этого потока, проходя через этот поток один раз.
Ясно, что вы можете подойти к нему с помощью хэширования или сортировки, но с потенциально бесконечным потоком вы можете явно исчерпать память. Так что вы должны сделать что-то умное здесь.
Элемент контрольного пакета - это элемент, размер которого превышает половину размера массива. Это означает, что мажоритарный элемент встречается чаще, чем все остальные элементы вместе взятые. То есть, если вы посчитаете, сколько раз появляется элемент контрольного числа, и вычтете количество вхождений всех остальных элементов, вы получите положительное число.
Поэтому, если вы посчитаете вхождения некоторого элемента, вычтете количество вхождений всех других элементов и получите число 0 - тогда ваш исходный элемент не может быть элементом большинства. Это основа для правильного алгоритма:
Объявите две переменные, counter и возможных_элементов. Итерируйте поток, если счетчик равен 0 - перезаписать возможный элемент и инициализировать счетчик, если число совпадает с возможным элементом - увеличить счетчик, иначе уменьшить его. Код 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) с очень маленькой константой перед O(n) (например, 3). Также похоже, что сложность пространства равна O(1), потому что у нас только три инициализированные переменные. Проблема в том, что одна из этих переменных является счетчиком, который потенциально может возрасти до n (когда массив состоит из одинаковых чисел). А для хранения числа n вам понадобится O(log (n)) место. Таким образом, с теоретической точки зрения это O(n) время и O(log(n)) пространство. Из практического, вы можете поместить 2 ^ 128 число в longint, и это количество элементов в массиве невообразимо огромен.
Также обратите внимание, что алгоритм работает, только если есть элемент контрольного числа. Если такого элемента не существует, он все равно вернет некоторое число, что, несомненно, будет неправильным. (алгоритм легко модифицировать, чтобы определить, существует ли мажоритарный элемент)
Канал истории: этот алгоритм был изобретен где-то в 1982 году Бойером, Муром и назван алгоритмом большинства голосов Бойера-Мура.
Ответ 4
Элемент большинства:
Массивный элемент в массиве A [] размера n - это элемент, который появляется более n/2 раза (и, следовательно, существует не более одного такого элемента).
Поиск кандидата:
Алгоритм для первой фазы, который работает в O (n), известен как Алгоритм голосования Мурса. Основная идея алгоритма заключается в том, что мы отменяем каждое вхождение элемента 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]
Выше алгоритма проходит через каждый элемент и поддерживает счетчик [maj_index]. Если следующий элемент тот же, то увеличивает счетчик, если следующий элемент не является таким же, а затем уменьшает счетчик, а если счетчик достигает 0, то изменяется maj_index к текущему элементу и устанавливает значение 1. Алгоритм первой фазы дает нам элемент-кандидат. На втором этапе нам нужно проверить, действительно ли кандидат является элементом большинства.
Вторая фаза проста и может быть легко выполнена в O (n). Нам просто нужно проверить, больше ли количество элементов-кандидатов больше n/2.
Подробнее читайте geeksforgeeks
Ответ 5
Время: О (п)
пространство: О (п)
Пройдите дерево и подсчитайте появление элементов в хеш-таблице.
Время: O (n lg n) или O (n * m) (зависит от используемой сортировки)
пробел: (1)
сортировать массив, а затем подсчитывать вхождения элементов.
Правильный ответ интервью: Алгоритм голосования Moores
Время: O (n)
Площадь: O (1)
Пройдите список, сравнивая текущее число с текущим лучшим количеством предположений. Если число равно текущему числу наилучшего приближения, счетчик, в противном случае уменьшите счетчик, и если счетчик достигнет нуля, замените текущий номер наилучшего предположения на текущий номер и установите счетчик на 1. Когда вы дойдете до конца, текущий Лучше всего догадаться, номер кандидата, снова перейдите в список, просто подсчитав экземпляры кандидата. Если конечный счетчик больше n/2, то это число большинства, в противном случае оно отсутствует.
Ответ 6
Как насчет метода случайной выборки? Вы можете пробовать, скажем, элементы sqrt (n) и для каждого элемента, который произошел больше, чем sqrt (n)/4 раза (может быть выполнено наивно в O (n) время и O (sqrt (n)) пробел), вы можете проверить был ли он элементом большинства в O (n) времени.
Этот метод находит большинство с большой вероятностью, потому что элемент большинства будет отбираться по крайней мере в sqrt (n)/2 раза в ожидании со стандартным отклонением не более n ^ {1/4}/2.
Другой подход к выборке, подобный подходу, который я видел в одной из дублирующих ссылок, состоит в том, чтобы нарисовать два образца, и если они равны, проверьте, что вы нашли элемент большинства в O (n) времени. Дополнительный этап проверки необходим, потому что другие элементы, кроме большинства, могут не отличаться.
Ответ 7
В алгоритме Монте-Карло
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)
}
Ответ 8
Чтобы найти большую часть элемента в массиве, вы можете использовать Алгоритм голосования большинства Мура, который является одним из лучших алгоритмов для него.
Сложность времени: O(n) or linear time
Космическая сложность: O(1) or constant space
Подробнее в Алгоритм голосования большинства Мура и GeeksforGeeks
Ответ 9
Если вам разрешено создавать хеш-таблицу и предполагать, что поиск хеш-записей постоянный, вы просто hash_map каждую запись против количества вхождений.
Вы можете сделать второй проход через таблицу, в которой вы получите тот, у которого наибольший счет, но если вы заранее знаете количество элементов в таблице, вы сразу узнаете, если у нас есть элемент мажориты на первом проходе, когда мы нажимаем нужный счет на элемент.
Конечно, вы не можете гарантировать, что существует даже последовательность из двух последовательных вхождений элемента, например, 1010101010101010101 не имеет последовательных 1, но это элемент большинства.
Нам ничего не говорят о том, существует ли какой-либо порядок в типе элемента, хотя, очевидно, мы должны иметь возможность сравнивать два для равенства.
Ответ 10
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)
Ответ 11
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;
}
}
}
}
Ответ 12
Измененная версия Boyer Algorithm,
- 3 проходит, где,
- В первом проходе мы выполняем форсированную итерацию массива
- Во втором проходе мы делаем обратную итерацию массива.
- В третьем проходе получите счетчики для большинства элементов, полученных в первом и втором проходах.
Технически алгоритм линейной сложности (O (3n)). Я считаю, что это должно работать для массива с мажоритарным элементом, который встречается не менее n/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;
}
Ответ 13
Спасибо за предыдущие ответы, которые вдохновили меня на знание Bob Boyer algo.:)
Общая версия Java: модифицированная версия алгоритма Boyer
Примечание: массив примитивного типа может использовать оболочку.
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();
}
}
Ответ 14
//Предположим, что нам задан массив A. // Если у нас есть все элементы в данном массиве, то каждый элемент меньше K, тогда мы можем создать дополнительный массив B с длиной K + 1.
//Инициализировать значение для каждого индекса массива с помощью 0. // Затем итерируем через данный массив A для каждого значения массива A [i], увеличиваем значение с помощью 1 с соответствующим индексом A [i] в созданном массиве B.
//После итерации через массив A, теперь итерации через массив B и найти максимальное значение. Если вы найдете значение больше, чем n/2, верните этот конкретный индекс.
//Сложность времени будет O (n + K), если K <= n, тогда эквивалентное 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));
}
}
Ответ 15
Это поможет вам, и если два элемента будут повторяться одинаковое количество раз, если не будет отображаться ни один из них.
int findCandidate(int a[], int size)
{
int count,temp=0,i,j, maj;
for (i = 0; i < size; i++) {
count=0;
for(j=i;j<size;j++)
{
if(a[j]==a[i])
count++;
}
if(count>temp)
{
temp=count;
maj=i;
}
else if(count==temp)
{
maj=-1;
}
}
return maj;
}
Ответ 16
Вот как я делаю это в C++, используя vector и multimap (JSON с ключами повтора).
#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
Ответ 17
Используйте Разделяй и властвуй, чтобы найти элемент большинства. Если мы разделим массив на две половины, мажоритарный элемент должен быть большинством в одной из половин. Если мы пойдем дальше и скомбинируем вложенные массивы, мы сможем выяснить, является ли элемент контрольного пакета также большинством объединенного массива. Это имеет сложность O (nlogN).
Вот реализация C++:
#include <algorithm>
#include <iostream>
#include <vector>
using std::vector;
// return the count of elem in the array
int count(vector <int> &a, int elem, int low, int high)
{
if (elem == -1) {
return -1;
}
int num = 0;
for (int i = low; i <= high; i++) {
if (a[i] == elem) {
num++;
}
}
return num;
}
// return the majority element of combined sub-array. If no majority return -1
int combined(vector <int> &a, int maj1, int maj2, int low, int mid, int high)
{
// if both sub arrays have same majority elem then we can safely say
// the entire array has same majority elem.
// NOTE: No majority ie. -1 will be taken care too
if (maj1 == maj2) {
return maj1;
}
// Conflicting majorities
if (maj1 != maj2) {
// Find the count of each maj1 and maj2 in complete array
int num_maj1 = count(a, maj1, low, high);
int num_maj2 = count(a, maj2, low, high);
if (num_maj1 == num_maj2) {
return -1;
}
int half = (high - low + 1) / 2;
if (num_maj1 > half) {
return maj1;
} else if (num_maj2 > half) {
return maj2;
}
}
return -1;
}
// Divide the array into 2 sub-arrays. If we have a majority element, then it
// should be a majority in at least one of the half. In combine step we will
// check if this majority element is majority of the combination of sub-arrays.
// array a and low is lower index and high is the higher index of array
int get_majority_elem(vector<int> &a, int low, int high)
{
if (low > high) return -1;
if (low == high) return a[low];
int mid = (low + high) / 2;
int h1 = get_majority_elem(a, low, mid);
int h2 = get_majority_elem(a, mid + 1, high);
// calculate the majority from combined sub arrays
int me = combined(a, h1, h2, low, mid, high);
return me;
}
Ответ 18
Сортировка заданного массива: O (nlogn).
Если размер массива равен 7, то элемент большинства имеет наименьший потолок (7/2) = 4 раза в массиве.
После сортировки массива это означает, что если элемент большинства сначала находится в позиции 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).