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

Question

Мажоритарный элемент - это элемент, размер которого превышает половину массива.

Как найти мажоритарный элемент в массиве в O(n)?

Пример ввода:

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

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

2

Answer 1

Это поможет вам, и если два элемента повторяются одинаковое количество раз, если не будет отображаться ни один

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

Answer 2

// Предположим, нам дан массив A. // Если у нас есть все элементы в данном массиве, каждый элемент меньше K, то мы можем создать дополнительный массив B длиной K + 1.

// Инициализировать значение для каждого индекса массива с 0. // Затем итерация по заданному массиву A для каждого значения массива A [i] увеличивает значение на 1 с соответствующим индексом A [i] в ​​созданном массиве B.

// После перебора массива A теперь перебираем массив B и находим максимальное значение. Если вы найдете значение больше n / 2, верните этот конкретный индекс.

// Сложность времени будет O (n + K), если K <= n, то эквивалентно O (n). </p>

// У нас есть ограничение, что все элементы массива 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 3

Спасибо за предыдущие ответы, которые вдохновили меня узнать Алгоритм Боба Бойера. :)

Универсальная версия 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 4

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

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

Код, протестированный здесь

Answer 5

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 6

    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)

Answer 7

Сортировать указанный массив: 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).

Answer 8

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

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

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

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