Рубрики

Элемент большинства

Напишите функцию, которая принимает массив и печатает мажоритарный элемент (если он существует), в противном случае выводится «No Majority Element». Элемент большинства в массиве A [] размера n — это элемент, который появляется более чем в n / 2 раза (и, следовательно, существует не более одного такого элемента).
Примеры :

Input : {3, 3, 4, 2, 4, 4, 2, 4, 4}
Output : 4 

Input : {3, 3, 4, 2, 4, 4, 2, 4}
Output : No Majority Element

МЕТОД 1 (базовый)
Основное решение состоит в том, чтобы иметь два цикла и отслеживать максимальное количество для всех различных элементов. Если максимальное число становится больше, чем n / 2, то разорвать циклы и вернуть элемент, имеющий максимальное количество. Если максимальное количество не становится больше, чем n / 2, то элемент мажоритарности не существует.
Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ программа для поиска большинства
// элемент в массиве
#include <bits/stdc++.h>

using namespace std;

  
// Функция для поиска элемента Majority
// в массиве

void findMajority(int arr[], int n)

{

    int maxCount = 0; 

    int index = -1; // стражи

    for(int i = 0; i < n; i++)

    {

        int count = 0;

        for(int j = 0; j < n; j++)

        {

            if(arr[i] == arr[j])

            count++;

        }

          

        // обновляем maxCount, если количество

        // текущий элемент больше

        if(count > maxCount)

        {

            maxCount = count;

            index = i;

        }

    }

      

    // если maxCount больше n / 2

    // вернуть соответствующий элемент

    if (maxCount > n/2)

       cout << arr[index] << endl;

      

    else

        cout << "No Majority Element" << endl;

}

  
// Код драйвера

int main()

{

    int arr[] = {1, 1, 2, 1, 3, 5, 1};

    int n = sizeof(arr) / sizeof(arr[0]);

      

    // вызов функции

    findMajority(arr, n);

  

    return 0;

}

Джава

// Java программа для поиска большинства
// элемент в массиве

  

import java.io.*;

  

class GFG {

      
// Функция для поиска элемента Majority
// в массиве

static void findMajority(int arr[], int n) 

    int maxCount = 0

    int index = -1; // стражи

    for(int i = 0; i < n; i++) 

    

        int count = 0

        for(int j = 0; j < n; j++) 

        

            if(arr[i] == arr[j]) 

            count++; 

        

          

        // обновляем maxCount, если количество

        // текущий элемент больше

        if(count > maxCount) 

        

            maxCount = count; 

            index = i; 

        

    

      

    // если maxCount больше n / 2

    // вернуть соответствующий элемент

    if (maxCount > n/2

    System.out.println (arr[index]); 

      

    else

    System.out.println ("No Majority Element"); 

  
// Код драйвера

    public static void main (String[] args) {

  

        int arr[] = {1, 1, 2, 1, 3, 5, 1}; 

        int n = arr.length; 

      

    // вызов функции

    findMajority(arr, n); 

    }

// Этот код предоставлен ajit.
}

Python 3

# Python 3 программа для поиска большинства
# элемент в массиве

  
# Функция найти большинство
# элемент в массиве

def findMajority(arr, n):

  

    maxCount = 0;

    index = -1 # стражи

    for i in range(n):

      

        count = 0

        for j in range(n):

          

            if(arr[i] == arr[j]):

                count += 1

          

        # обновить maxCount, если количество

        # текущий элемент больше

        if(count > maxCount):

          

            maxCount = count

            index = i

      

    # если maxCount больше n / 2

    # вернуть соответствующий элемент

    if (maxCount > n//2):

        print(arr[index])

      

    else:

        print("No Majority Element")

  
# Код драйвера

if __name__ == "__main__":

    arr = [1, 1, 2, 1, 3, 5, 1]

    n = len(arr)

      

    # Вызов функции

    findMajority(arr, n)

  
# Этот код добавлен
# by ChitraNayal

C #

// C # программа для поиска большинства
// элемент в массиве

using System;

  

public class GFG{

          
// Функция для поиска элемента Majority
// в массиве

static void findMajority(int []arr, int n) 

    int maxCount = 0; 

    int index = -1; // стражи

    for(int i = 0; i < n; i++) 

    

        int count = 0; 

        for(int j = 0; j < n; j++) 

        

            if(arr[i] == arr[j]) 

            count++; 

        

          

        // обновляем maxCount, если количество

        // текущий элемент больше

        if(count > maxCount) 

        

            maxCount = count; 

            index = i; 

        

    

      

    // если maxCount больше n / 2

    // вернуть соответствующий элемент

    if (maxCount > n/2) 

    Console.WriteLine (arr[index]); 

      

    else

    Console.WriteLine("No Majority Element"); 

  
// Код драйвера

    static public void Main (){

          

        int []arr = {1, 1, 2, 1, 3, 5, 1}; 

        int n = arr.Length; 

      

        // вызов функции

        findMajority(arr, n); 

    }

// Этот код предоставлен Tushil ..
}

PHP

<?php
// PHP программа для поиска большинства
// элемент в массиве

  
// Функция для поиска элемента Majority
// в массиве

function findMajority($arr, $n)

{

    $maxCount = 0; 

    $index = -1; // стражи

    for($i = 0; $i < $n; $i++)

    {

        $count = 0;

        for($j = 0; $j < $n; $j++)

        {

            if($arr[$i] == $arr[$j])

            $count++;

        }

          

        // обновляем maxCount, если количество

        // текущий элемент больше

        if($count > $maxCount)

        {

            $maxCount = $count;

            $index = $i;

        }

    }

      

    // если maxCount больше n / 2

    // вернуть соответствующий элемент

    if ($maxCount > $n/2)

        echo $arr[$index] . "\n";

    else

        echo "No Majority Element" . "\n";

}

  
// Код драйвера

$arr = array(1, 1, 2, 1, 3, 5, 1);

$n = sizeof($arr);

      
// вызов функции

findMajority($arr, $n);

  
// Этот код добавлен
// Аканкша Рай


Выход :

1

Сложность времени: O (n * n).
Вспомогательное пространство: O (1).

МЕТОД 2 (Использование бинарного дерева поиска )

Вставьте элементы в BST один за другим, и если элемент уже присутствует, увеличьте счетчик узла. На любом этапе, если число узлов становится больше, чем n / 2, затем возвращается.
Метод хорошо работает для случаев, когда n / 2 + 1 вхождений мажоритарного элемента присутствует в начале массива, например {1, 1, 1, 1, 1, 2, 3, 4}.

Сложность времени:
если используется дерево бинарного поиска, то сложность времени будет O (n ^ 2). Если используется дерево самобалансирующегося бинарного поиска, тогда O (nlogn)
Вспомогательное пространство: O (n)

МЕТОД 3 (Использование алгоритма голосования Мура)
Это двухступенчатый процесс.

ПРИМЕЧАНИЕ. Этот метод работает только в том случае, если нам известно, что элемент контрольного пакета существует в массиве, в противном случае этот метод не будет работать, так как в определении проблемы мы говорили, что элемент контрольного пакета может существовать или не существовать, но для применения этого подхода можно предположить, что этот мажоритарный элемент существует в данном входном массиве

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

1. Нахождение кандидата:
Алгоритм первой фазы, который работает в 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.

Пример :
Пусть массив будет A [] = 2, 2, 3, 5, 2, 2, 6

  • Initialize maj_index = 0, count = 1
  • Следующий элемент равен 2, что совпадает с [maj_index] => count = 2
  • Следующий элемент 3, который отличается от [maj_index] => count = 1
  • Следующий элемент 5, который отличается от [maj_index] => count = 0
    Поскольку count = 0, измените кандидата на мажоритарный элемент на 5 => maj_index = 3, count = 1
  • Следующий элемент равен 2, что отличается от [maj_index] => count = 0
    Так как count = 0, измените кандидата на мажоритарный элемент на 2 => maj_index = 4
  • Следующий элемент равен 2, что совпадает с [maj_index] => count = 2
  • Следующий элемент 6, который отличается от [maj_index] => count = 1
  • Наконец, кандидат на мажоритарный элемент — 2.

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

2. Проверьте, является ли элемент, полученный на шаге 1, мажоритарным или нет:

printMajority (a[], size)
1.  Find the candidate for majority
2.  If candidate is majority. i.e., appears more than n/2 times.
       Print the candidate
3.  Else
       Print "No Majority Element"

Ниже приведена реализация вышеуказанного подхода:

C ++

/ * C ++ Программа для выяснения

   мажоритарный элемент в массиве * /

#include <bits/stdc++.h>

using namespace std;

  
/ * Функция поиска кандидата на большинство * /

int findCandidate(int a[], int size)

{

    int maj_index = 0, count = 1;

    for (int i = 1; i < size; i++)

    {

        if (a[maj_index] == a[i])

            count++;

        else

            count--;

        if (count == 0)

        {

            maj_index = i;

            count = 1;

        }

    }

    return a[maj_index];

}

  
/ * Функция, чтобы проверить, если кандидат

   встречается более n / 2 раза * /

bool isMajority(int a[], int size, int cand)

{

    int count = 0;

    for (int i = 0; i < size; i++)

      

    if (a[i] == cand)

    count++;

          

    if (count > size/2)

    return 1;

      

    else

    return 0;

}

  
/ * Функция для печати мажоритарного элемента * /

void printMajority(int a[], int size)

{

   / * Найти кандидата на большинство * /

   int cand = findCandidate(a, size);

  

   / * Распечатать кандидата, если это большинство * /

   if (isMajority(a, size, cand))

   cout << " " << cand << " ";

     

   else

   cout << "No Majority Element";

}

  

  
/ * Функция драйвера для проверки вышеуказанных функций * /

int main()

{

    int a[] = {1, 3, 3, 1, 2};

    int size = (sizeof(a))/sizeof(a[0]);

      

    // вызов функции

    printMajority(a, size);

      

    return 0;

}

С

/ * Программа для определения большинства элементов в массиве * /
# include<stdio.h>
# define bool int

  

int findCandidate(int *, int);

bool isMajority(int *, int, int);

  
/ * Функция для печати мажоритарного элемента * /

void printMajority(int a[], int size)

{

  / * Найти кандидата на большинство * /

  int cand = findCandidate(a, size);

  

  / * Распечатать кандидата, если это большинство * /

  if (isMajority(a, size, cand))

    printf(" %d ", cand);

  else

    printf("No Majority Element");

}

  
/ * Функция поиска кандидата на большинство * /

int findCandidate(int a[], int size)

{

    int maj_index = 0, count = 1;

    int i;

    for (i = 1; i < size; i++)

    {

        if (a[maj_index] == a[i])

            count++;

        else

            count--;

        if (count == 0)

        {

            maj_index = i;

            count = 1;

        }

    }

    return a[maj_index];

}

  
/ * Функция для проверки, если кандидат встречается более n / 2 раза * /

bool isMajority(int a[], int size, int cand)

{

    int i, count = 0;

    for (i = 0; i < size; i++)

      if (a[i] == cand)

         count++;

    if (count > size/2)

       return 1;

    else

       return 0;

}

  
/ * Функция драйвера для проверки вышеуказанных функций * /

int main()

{

    int a[] = {1, 3, 3, 1, 2};

    int size = (sizeof(a))/sizeof(a[0]);

    printMajority(a, size);

    getchar();

    return 0;

}

Джава

/ * Программа для определения большинства элементов в массиве * /

  

class MajorityElement 

{

    / * Функция для печати мажоритарного элемента * /

    void printMajority(int a[], int size) 

    {

        / * Найти кандидата на большинство * /

        int cand = findCandidate(a, size);

  

        / * Распечатать кандидата, если это большинство * /

        if (isMajority(a, size, cand))

            System.out.println(" " + cand + " ");

        else 

            System.out.println("No Majority Element");

    }

  

    / * Функция поиска кандидата на большинство * /

    int findCandidate(int a[], int size) 

    {

        int maj_index = 0, count = 1;

        int i;

        for (i = 1; i < size; i++) 

        {

            if (a[maj_index] == a[i])

                count++;

            else

                count--;

            if (count == 0)

            {

                maj_index = i;

                count = 1;

            }

        }

        return a[maj_index];

    }

  

    / * Функция, чтобы проверить, появляется ли кандидат больше

       чем н / 2 раза * /

    boolean isMajority(int a[], int size, int cand) 

    {

        int i, count = 0;

        for (i = 0; i < size; i++) 

        {

            if (a[i] == cand)

                count++;

        }

        if (count > size / 2

            return true;

        else

            return false;

    }

  

    / * Программа драйвера для проверки вышеуказанных функций * /

    public static void main(String[] args) 

    {

        MajorityElement majorelement = new MajorityElement();

        int a[] = new int[]{1, 3, 3, 1, 2};

        int size = a.length;

        majorelement.printMajority(a, size);

    }

}

  
// Этот код предоставлен Mayank Jaiswal

питон

# Программа для определения большинства элементов в массиве

  
# Функция поиска кандидата на большинство

def findCandidate(A):

    maj_index = 0

    count = 1

    for i in range(len(A)):

        if A[maj_index] == A[i]:

            count += 1

        else:

            count -= 1

        if count == 0:

            maj_index = i

            count = 1

    return A[maj_index]

  
# Функция для проверки, если кандидат встречается более n / 2 раза

def isMajority(A, cand):

    count = 0

    for i in range(len(A)):

        if A[i] == cand:

            count += 1

    if count > len(A)/2:

        return True

    else:

        return False

  
# Функция для печати большинства элемента

def printMajority(A):

    # Найти кандидата на большинство

    cand = findCandidate(A)

      

    # Распечатать кандидата, если это большинство

    if isMajority(A, cand) == True:

        print(cand)

    else:

        print("No Majority Element")

  
# Драйверная программа для проверки вышеуказанных функций

A = [1, 3, 3, 1, 2]

printMajority(A) 

C #

// C # Программа для определения большинства элементов в массиве

using System;

  

class GFG

{

    / * Функция для печати мажоритарного элемента * /

    static void printMajority(int []a, int size) 

    {

        / * Найти кандидата на большинство * /

        int cand = findCandidate(a, size);

  

        / * Распечатать кандидата, если это большинство * /

        if (isMajority(a, size, cand))

            Console.Write(" " + cand + " ");

        else

            Console.Write("No Majority Element");

    }

  

    / * Функция поиска кандидата на большинство * /

    static int findCandidate(int []a, int size) 

    {

        int maj_index = 0, count = 1;

        int i;

        for (i = 1; i < size; i++) 

        {

            if (a[maj_index] == a[i])

                count++;

            else

                count--;

                  

            if (count == 0)

            {

                maj_index = i;

                count = 1;

            }

        }

        return a[maj_index];

    }

  

    // Функция для проверки, если кандидат

    // встречается более n / 2 раза

    static bool isMajority(int []a, int size, int cand) 

    {

        int i, count = 0;

        for (i = 0; i < size; i++) 

        {

            if (a[i] == cand)

                count++;

        }

        if (count > size / 2) 

            return true;

        else

            return false;

    }

  

    // Код драйвера

    public static void Main() 

    {

          

        int []a = {1, 3, 3, 1, 2};

        int size = a.Length;

        printMajority(a, size);

    }

}

  
// Этот код предоставлен Sam007

PHP

<?php
// PHP программа для выявления большинства
// элемент в массиве

  
// Функция для поиска кандидата
// для большинства

function findCandidate($a, $size)

{

    $maj_index = 0;

    $count = 1;

    for ($i = 1; $i < $size; $i++)

    {

        if ($a[$maj_index] == $a[$i])

            $count++;

        else

            $count--;

        if ($count == 0)

        {

            $maj_index = $i;

            $count = 1;

        }

    }

    return $a[$maj_index];

}

  
// Функция для проверки, если кандидат
// встречается более n / 2 раза

function isMajority($a, $size, $cand)

{

    $count = 0;

    for ($i = 0; $i < $size; $i++)

      

    if ($a[$i] == $cand)

    $count++;

          

    if ($count > $size / 2)

    return 1;

      

    else

    return 0;

}

  
// Функция для печати большинства элемента

function printMajority($a, $size)

{

    / * Найти кандидата на большинство * /

    $cand = findCandidate($a, $size);

      

    / * Распечатать кандидата, если это большинство * /

    if (isMajority($a, $size, $cand))

        echo " ", $cand, " ";

    else

        echo "No Majority Element";

}

  
// Код драйвера

$a = array(1, 3, 3, 1, 2);

$size = sizeof($a);

  
// вызов функции

printMajority($a, $size);

  
// Этот код предоставлен jit_t
?>


Выход:

No Majority Element 

Сложность времени: O (n)
Вспомогательное пространство: O (1)

МЕТОД 4 (Использование Hashmap): Этот метод несколько похож на алгоритм голосования Мура с точки зрения сложности времени, но в этом случае нет необходимости во втором шаге алгоритма голосования Мура. Но, как обычно, здесь сложность пространства становится O (n) ,
В Hashmap (пара ключ-значение) при значении сохраняют счетчик для каждого элемента (ключа), и всякий раз, когда счетчик превышает половину длины массива, мы просто возвращаем этот ключ (мажоритарный элемент).

Сложность времени: O (n)
Вспомогательное пространство: O (n)

Ниже приведена реализация.

C ++

/ * C ++ программа для выявления большинства
элемент в массиве * /
#include <bits/stdc++.h>

using namespace std;

  

void findMajority(int arr[], int size)

{

    unordered_map<int, int> m;

    for(int i = 0; i < size; i++)

        m[arr[i]]++;

    int count = 0;

    for(auto i : m)

    {

        if(i.second > size / 2)

        {

            count =1;

            cout << "Majority found :- " << i.first<<endl;

            break;

        }

    }

    if(count == 0)

        cout << "No Majority element" << endl;

}

  
// Код драйвера

int main() 

    int arr[] = {2, 2, 2, 2, 5, 5, 2, 3, 3}; 

    int n = sizeof(arr) / sizeof(arr[0]); 

      

    // вызов функции

    findMajority(arr, n); 

  

    return 0; 

  
// Этот код предоставлен codeMan_d

Джава

import java.util.HashMap;

  
/ * Программа для определения большинства элементов в массиве * /

   

class MajorityElement 

{

    private static void findMajority(int[] arr) 

    {

        HashMap<Integer,Integer> map = new HashMap<Integer, Integer>();

  

        for(int i = 0; i < arr.length; i++) {

            if (map.containsKey(arr[i])) {

                    int count = map.get(arr[i]) +1;

                    if (count > arr.length /2) {

                        System.out.println("Majority found :- " + arr[i]);

                        return;

                    } else

                        map.put(arr[i], count);

  

            }

            else

                map.put(arr[i],1);

            }

            System.out.println(" No Majority element");

    }

  

   

    / * Программа драйвера для проверки вышеуказанных функций * /

    public static void main(String[] args) 

    {

        int a[] = new int[]{2,2,2,2,5,5,2,3,3};

          

        findMajority(a);

    }

}
// Этот код предоставлен Караном Малхотрой

python3

# Python программа для выяснения большинства
# элемент в массиве

  

def findMajority(arr, size):

    m = {}

    for i in range(size):

        if arr[i] in m:

            m[arr[i]] += 1

        else:

            m[arr[i]] = 1

    count = 0

    for key in m:

        if m[key] > size / 2:

            count = 1

            print("Majority found :-",key)

            break

    if(count == 0):

        print("No Majority element")

  
# Код драйвера

arr = [2, 2, 2, 2, 5, 5, 2, 3, 3

n = len(arr)

  
# Вызов функции
findMajority(arr, n)

  
# Этот код предоставлен ankush_953

C #

// C # Программа для выяснения большинства
// элемент в массиве

using System;

using System.Collections.Generic;

  

class GFG

{

private static void findMajority(int[] arr)

{

    Dictionary<int

               int> map = new Dictionary<int

                                         int>();

  

    for (int i = 0; i < arr.Length; i++)

    {

        if (map.ContainsKey(arr[i]))

        {

                int count = map[arr[i]] + 1;

                if (count > arr.Length / 2)

                {

                    Console.WriteLine("Majority found :- "

                                                    arr[i]);

                    return;

                }

                else

                {

                    map[arr[i]] = count;

                }

  

        }

        else

        {

            map[arr[i]] = 1;

        }

    }

    Console.WriteLine(" No Majority element");

}

  

  
// Код драйвера

public static void Main(string[] args)

{

    int[] a = new int[]{2, 2, 2, 2, 

                        5, 5, 2, 3, 3};

  

    findMajority(a);

}
}

  
// Этот код предоставлен Shrikant13

Выход:

Majority found :- 2

Спасибо Ашвани Танвар, Каран Малхотра за предложение.


Сейчас попробуй ниже вопрос

Дан массив из 2n элементов, из которых n элементов одинаковы, а остальные n элементов различны. Напишите программу на C, чтобы узнать значение, которое присутствует в массиве n раз. Нет никаких ограничений на элементы в массиве. Они случайные (в частности, они не последовательные).

Рекомендуемые посты:

Элемент большинства

0.00 (0%) 0 votes