Найти элемент большинства в массиве

Question

Элемент most - это элемент, который содержит более половины размера массива.

Как найти элемент большинства в массиве в O(n)?

Пример входные данные:

{2,1,2,3,4,2,1,2,2} 

Ожидаемые результаты:

2 

Answer 1

Большинство элемента (если он существует) будут также медианой. Мы можем найти медиану в O (n), а затем проверить, что она действительно является мажоритарным элементом в O (n). Дополнительная информация для реализации link

Answer 2

Как насчет случайного подхода к выборке? Вы можете пробовать, скажем, элементы sqrt (n) и для каждого элемента, который произошел больше, чем sqrt (n)/4 раза (может быть выполнено наивно в O (n) время и O (sqrt (n)) пробел), вы можете проверить был ли он элементом большинства в O (n) времени.

Этот метод находит большинство с высокой вероятностью, потому что элемент большинства будет выборку, по меньшей мере SQRT (N)/2 раз в ожидании, со стандартным отклонением не более N^{1/4}/2.

Другой подход к выборке, подобный подходу, который я видел в одном из дублирующих ссылок, состоит в том, чтобы нарисовать два образца, и если они равны, проверьте, что вы нашли элемент большинства в O (n) времени. Дополнительный этап проверки необходим, потому что другие элементы, кроме большинства, могут не отличаться.

Answer 3

Если вам разрешено создавать хеш-таблицу и предполагается, что поиск в хэш-записи постоянный, вы просто hash_map каждую запись против количества вхождений.

Вы можете сделать второй проход по таблице, в котором вы получите тот, у которого есть наибольший счет, но если вы заранее знаете количество элементов в таблице, вы сразу узнаете, если у нас есть элемент мажориты на первом проходе когда мы нажмем нужный счет на элемент.

Вы не можете гарантировать, конечно, что существует даже последовательность из двух последовательных вхождений элемента, например, 1010101010101010101 не имеет последовательных 1, но это элемент большинства.

Нам ничего не говорят о том, существует ли какой-либо порядок в типе элемента, хотя, очевидно, мы должны иметь возможность сравнивать два для равенства.

Answer 4

// 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; 
} 

Answer 5

Время: О (п)

пространство: О (п)

Прогулка по дереву и считать возникновение элементов в хэш-таблице.

Время: О (п Л.Г. п) или О (п * м) (в зависимости от вида используемого)

пространство: (1)

сортировать массив затем подсчитать вхождения элементов.

Интервью Правильный ответ: Мур Голосование Алгоритм

Время: O (п)

Space: O (1)

Прогулка список сравнения текущий номер против текущего лучшего числа догадок. Если число равно текущему числу наилучшего приближения, счетчик, в противном случае уменьшите счетчик, и если счетчик достигнет нуля, замените текущий номер наилучшего предположения на текущий номер и установите счетчик на 1. Когда вы дойдете до конца, текущий Лучше всего догадаться, номер кандидата, снова перейдите в список, просто подсчитав экземпляры кандидата. Если конечный счет больше n/2, то это число большинства, в противном случае его нет.

Answer 6

Сортировка данного массива: O (nlogn).

Если размер массива равен 7, то элемент большинства имеет наименьший потолок (7/2) = 4 раза в массиве.

После сортировки массива это означает, что если элемент большинства сначала находится в позиции i, он также находится в позиции i + floor (7/2) (4 вхождения).

Пример - Учитывая массив А - {7,3,2,3,3,6,3}

Сортировка массива - {2,3,3,3,3,6,7}

Элемент 3 находится в позиции 1 (индекс массива, начиная с 0.) Если позиция 1 + 3 = 4-й элемент также равно 3, то это означает, что 3 является элементом большинства.

если цикл через массив от начала ..

сравнить положение-с позицией 3, различными элементами 2 и 3. сравните положение-с позицией 4, тот же элементом. Мы нашли наш мажоритарный матч!

Сложность - О (п)

Общее время сложность - О (п).

Answer 7

Большинство Элемент:

Большинство элемент массива А [] размера п является элементом, который появляется больше, чем п/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.

Read geeksforgeeks для более подробной информации

Answer 8

В алгоритме Монте-Карло,

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) 
    } 

Answer 9

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 (п)

Answer 10

Печально видеть что через 5 лет никто не написал надлежащего объяснение этой проблемы.

Это стандартная проблема в потоковых алгоритмах (где у вас огромный (потенциально бесконечный) поток данных), и вам приходится вычислять некоторые статистические данные из этого потока, проходя через этот поток один раз.

---

Очевидно, вы можете подойти к нему с хэширования или сортировки, но с потенциально бесконечным потоком можно явно запустить из памяти. Поэтому вам нужно сделать что-то умное здесь.

---

Большинство элементом является элемент, который встречается более половины размера массива. Это означает, что элемент большинства встречается больше, чем все остальные элементы вместе взятые. То есть, если вы подсчитаете количество раз, когда появляется элемент большинства, и вычтите количество вхождений всех других элементов, вы получите положительное число.

Итак, если вы подсчитаете вхождения какого-либо элемента и вычтите количество вхождений всех других элементов и получите число 0 - тогда ваш исходный элемент не может быть элементом большинства. Это является основой для правильного алгоритма:

Объявление двух переменных, счетчика и возможного_элемента. Итерируйте поток, если счетчик равен 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)) space. Таким образом, с теоретической точки зрения это O(n) время и O(log(n)) пространство. Из практического вы можете поместить число 2^128 в longint, и это количество элементов в массиве невообразимо огромно.

Также обратите внимание, что алгоритм работает только в том случае, если имеется элемент большинства. Если такой элемент не существует, он все равно вернет некоторое число, которое, безусловно, будет неправильным.(Легко модифицировать алгоритм, чтобы сказать, существует ли элемент большинства)

История канала: этот алгоритм был изобретен где-то в 1982 году Бойер, Мур и призвал Boyer–Moore majority vote algorithm

Answer 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; 
    } 
    } 


} 

}

Answer 12

A модифицированная версия Бойер Алгоритм,

• 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; 
} 

Code tested here

Answer 13

Спасибо за предыдущие ответы, которые вдохновили меня знать Bob Boyer's algo. :)

Java общая версия: модифицированная версия алгоритма Бойе

Примечание: массив примитивного типа может использование обертка.

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(); 
} 

}

Answer 14

Чтобы найти большинство элемента в массиве, то вы можете использовать большинство голосов алгоритм Мура, который является одним из лучших алгоритмов для него.

Время Сложность:O(n) or linear time

Space Сложность:O(1) or constant space

Узнайте больше на Moore's Majority Vote Algorithm и GeeksforGeeks

Answer 15

// Пусть дан массив А. // Если мы имеем все элементы в данном массиве, такие, что каждый элемент меньше 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)); 
    } 
} 

Answer 16

Это поможет вам, и если два элемента повторить то же число раз, если не покажет ничего.

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) 
{ printf("\n for:%d, %d>%d",a[i],count,temp); 
    temp=count; 
    maj=i; 
} 
else if(count==temp) 
{ printf("\n for:%d, %d=%d, at i=%d",a[i],count,temp,i); 
    maj=-1; 
} 
} 

printf("\n%d",a[maj]); 
return maj; 
}