Elemento mayoritario – Part 1

Escriba una función que tome una array e imprima el elemento mayoritario (si existe), de lo contrario, imprima «Sin elemento mayoritario». Un elemento mayoritario en una array A[] de tamaño n es un elemento que aparece más de n/2 veces (y, por lo tanto, hay como máximo uno de esos elementos). 

Ejemplos: 

C++

// C++ program to find Majority
// element in an array
#include <bits/stdc++.h>
using namespace std;
  
// Function to find Majority element
// in an array
void findMajority(int arr[], int n)
{
    int maxCount = 0;
    int index = -1; // sentinels
    for (int i = 0; i < n; i++) {
        int count = 0;
        for (int j = 0; j < n; j++) {
            if (arr[i] == arr[j])
                count++;
        }
  
        // update maxCount if count of
        // current element is greater
        if (count > maxCount) {
            maxCount = count;
            index = i;
        }
    }
  
    // if maxCount is greater than n/2
    // return the corresponding element
    if (maxCount > n / 2)
        cout << arr[index] << endl;
  
    else
        cout << "No Majority Element" << endl;
}
  
// Driver code
int main()
{
    int arr[] = { 1, 1, 2, 1, 3, 5, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
  
    // Function calling
    findMajority(arr, n);
  
    return 0;
}

Java

// Java program to find Majority
// element in an array
  
import java.io.*;
  
class GFG {
  
    // Function to find Majority element
    // in an array
    static void findMajority(int arr[], int n)
    {
        int maxCount = 0;
        int index = -1; // sentinels
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = 0; j < n; j++) {
                if (arr[i] == arr[j])
                    count++;
            }
  
            // update maxCount if count of
            // current element is greater
            if (count > maxCount) {
                maxCount = count;
                index = i;
            }
        }
  
        // if maxCount is greater than n/2
        // return the corresponding element
        if (maxCount > n / 2)
            System.out.println(arr[index]);
  
        else
            System.out.println("No Majority Element");
    }
  
    // Driver code
    public static void main(String[] args)
    {
  
        int arr[] = { 1, 1, 2, 1, 3, 5, 1 };
        int n = arr.length;
  
        // Function calling
        findMajority(arr, n);
    }
    // This code is contributed by ajit.
}

Python3

# Python3 program to find Majority
# element in an array
  
# Function to find Majority
# element in an array
  
  
def findMajority(arr, n):
  
    maxCount = 0
    index = -1  # sentinels
    for i in range(n):
  
        count = 0
        for j in range(n):
  
            if(arr[i] == arr[j]):
                count += 1
  
        # update maxCount if count of
        # current element is greater
        if(count > maxCount):
  
            maxCount = count
            index = i
  
    # if maxCount is greater than n/2
    # return the corresponding element
    if (maxCount > n//2):
        print(arr[index])
  
    else:
        print("No Majority Element")
  
  
# Driver code
if __name__ == "__main__":
    arr = [1, 1, 2, 1, 3, 5, 1]
    n = len(arr)
  
    # Function calling
    findMajority(arr, n)
  
# This code is contributed
# by ChitraNayal

C#

// C# program to find Majority
// element in an array
using System;
  
public class GFG {
  
    // Function to find Majority element
    // in an array
    static void findMajority(int[] arr, int n)
    {
        int maxCount = 0;
        int index = -1; // sentinels
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = 0; j < n; j++) {
                if (arr[i] == arr[j])
                    count++;
            }
  
            // update maxCount if count of
            // current element is greater
            if (count > maxCount) {
                maxCount = count;
                index = i;
            }
        }
  
        // if maxCount is greater than n/2
        // return the corresponding element
        if (maxCount > n / 2)
            Console.WriteLine(arr[index]);
  
        else
            Console.WriteLine("No Majority Element");
    }
  
    // Driver code
    static public void Main()
    {
  
        int[] arr = { 1, 1, 2, 1, 3, 5, 1 };
        int n = arr.Length;
  
        // Function calling
        findMajority(arr, n);
    }
    // This code is contributed by Tushil..
}

PHP

<?php
// PHP program to find Majority 
// element in an array
  
// Function to find Majority element
// in an array
function findMajority($arr, $n)
{
    $maxCount = 0; 
    $index = -1; // sentinels
    for($i = 0; $i < $n; $i++)
    {
        $count = 0;
        for($j = 0; $j < $n; $j++)
        {
            if($arr[$i] == $arr[$j])
            $count++;
        }
          
        // update maxCount if count of 
        // current element is greater
        if($count > $maxCount)
        {
            $maxCount = $count;
            $index = $i;
        }
    }
      
    // if maxCount is greater than n/2 
    // return the corresponding element 
    if ($maxCount > $n/2)
        echo $arr[$index] . "\n";
    else
        echo "No Majority Element" . "\n";
}
  
// Driver code
$arr = array(1, 1, 2, 1, 3, 5, 1);
$n = sizeof($arr);
      
// Function calling 
findMajority($arr, $n);
  
// This code is contributed 
// by Akanksha Rai

Javascript

<script>
  
// Javascript program to find Majority
// element in an array
  
// Function to find Majority element
// in an array
function findMajority(arr, n)
{
    let maxCount = 0;
    let index = -1; // sentinels
      
    for(let i = 0; i < n; i++) 
    {
        let count = 0;
        for(let j = 0; j < n; j++) 
        {
            if (arr[i] == arr[j])
                count++;
        }
  
        // Update maxCount if count of
        // current element is greater
        if (count > maxCount) 
        {
            maxCount = count;
            index = i;
        }
    }
  
    // If maxCount is greater than n/2
    // return the corresponding element
    if (maxCount > n / 2)
        document.write(arr[index]);
    else
        document.write("No Majority Element");
}
  
// Driver code
let arr = [ 1, 1, 2, 1, 3, 5, 1 ];
let n = arr.length;
  
// Function calling
findMajority(arr, n);
  
// This code is contributed by suresh07
  
</script>

C++14

// C++ program to demonstrate insert operation in binary
// search tree.
#include <bits/stdc++.h>
using namespace std;
  
struct node {
    int key;
    int c = 0;
    struct node *left, *right;
};
  
// A utility function to create a new BST node
struct node* newNode(int item)
{
    struct node* temp
        = (struct node*)malloc(sizeof(struct node));
    temp->key = item;
    temp->c = 1;
    temp->left = temp->right = NULL;
    return temp;
}
  
// A utility function to insert a new node with given key in
// BST
struct node* insert(struct node* node, int key, int& ma)
{
    // If the tree is empty, return a new node
    if (node == NULL) {
        if (ma == 0)
            ma = 1;
  
        return newNode(key);
    }
  
    // Otherwise, recur down the tree
    if (key < node->key)
        node->left = insert(node->left, key, ma);
    else if (key > node->key)
        node->right = insert(node->right, key, ma);
    else
        node->c++;
  
    // find the max count
    ma = max(ma, node->c);
  
    // return the (unchanged) node pointer
    return node;
}
  
// A utility function to do inorder traversal of BST
void inorder(struct node* root, int s)
{
    if (root != NULL) {
        inorder(root->left, s);
  
        if (root->c > (s / 2))
            printf("%d \n", root->key);
  
        inorder(root->right, s);
    }
}
// Driver Code
int main()
{
    int a[] = { 1, 3, 3, 3, 2 };
    int size = (sizeof(a)) / sizeof(a[0]);
  
    struct node* root = NULL;
    int ma = 0;
  
    for (int i = 0; i < size; i++) {
        root = insert(root, a[i], ma);
    }
  
    // Function call
    if (ma > (size / 2))
        inorder(root, size);
    else
        cout << "No majority element\n";
    return 0;
}

Java

// Java program to demonstrate insert 
// operation in binary search tree.
import java.io.*;
  
class Node
{
    int key;
    int c = 0;
    Node left,right;
      
}
class GFG{
      
static int ma = 0;
  
// A utility function to create a 
// new BST node
static Node newNode(int item)
{
    Node temp = new Node();
    temp.key = item;
    temp.c = 1;
    temp.left = temp.right = null;
    return temp;
}
  
// A utility function to insert a new node
// with given key in BST
static Node insert(Node node, int key)
{
      
    // If the tree is empty, 
    // return a new node
    if (node == null) 
    {
        if (ma == 0)
            ma = 1;
  
        return newNode(key);
    }
      
    // Otherwise, recur down the tree
    if (key < node.key)
        node.left = insert(node.left, key);
    else if (key > node.key)
        node.right = insert(node.right, key);
    else
        node.c++;
  
    // Find the max count
    ma = Math.max(ma, node.c);
   
    // Return the (unchanged) node pointer
    return node;
}
  
// A utility function to do inorder
// traversal of BST
static void inorder(Node root, int s)
{
    if (root != null) 
    {
        inorder(root.left, s);
  
        if (root.c > (s / 2))
            System.out.println(root.key + "\n");
  
        inorder(root.right, s);
    }
}
  
// Driver Code
public static void main(String[] args)
{
    int a[] = { 1, 3, 3, 3, 2 };
    int size = a.length;
    Node root = null;
      
    for(int i = 0; i < size; i++) 
    {
        root = insert(root, a[i]);
    }
      
    // Function call
    if (ma > (size / 2))
        inorder(root, size);
    else
        System.out.println("No majority element\n");
}
}
  
// This code is contributed by avanitrachhadiya2155

Python3

# Python3 program to demonstrate insert operation in binary
# search tree.
# class for creating node
class Node():
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
        self.count = 1  # count of number of times data is inserted in tree
  
# class for binary search tree
# it initialises tree with None root
# insert function inserts node as per BST rule
# and also checks for majority element
# if no majority element is found yet, it returns None
  
  
class BST():
    def __init__(self):
        self.root = None
  
    def insert(self, data, n):
        out = None
        if (self.root == None):
            self.root = Node(data)
        else:
            out = self.insertNode(self.root, data, n)
        return out
  
    def insertNode(self, currentNode, data, n):
        if (currentNode.data == data):
            currentNode.count += 1
            if (currentNode.count > n//2):
                return currentNode.data
            else:
                return None
        elif (currentNode.data < data):
            if (currentNode.right):
                self.insertNode(currentNode.right, data, n)
            else:
                currentNode.right = Node(data)
        elif (currentNode.data > data):
            if (currentNode.left):
                self.insertNode(currentNode.left, data, n)
            else:
                currentNode.left = Node(data)
  
  
# Driver code
# declaring an array
arr = [3, 2, 3]
n = len(arr)
  
# declaring None tree
tree = BST()
flag = 0
for i in range(n):
    out = tree.insert(arr[i], n)
    if (out != None):
        print(arr[i])
        flag = 1
        break
if (flag == 0):
    print("No Majority Element")

C#

// C# program to demonstrate insert 
// operation in binary search tree.
using System;
  
public class Node
{
    public int key;
    public int c = 0;
    public Node left,right;
       
}
  
class GFG{
      
static int ma = 0;
  
// A utility function to create a 
// new BST node
static Node newNode(int item)
{
    Node temp = new Node();
    temp.key = item;
    temp.c = 1;
    temp.left = temp.right = null;
    return temp;
}
   
// A utility function to insert a new node
// with given key in BST
static Node insert(Node node, int key)
{
      
    // If the tree is empty, 
    // return a new node
    if (node == null) 
    {
        if (ma == 0)
            ma = 1;
   
        return newNode(key);
    }
       
    // Otherwise, recur down the tree
    if (key < node.key)
        node.left = insert(node.left, key);
    else if (key > node.key)
        node.right = insert(node.right, key);
    else
        node.c++;
   
    // Find the max count
    ma = Math.Max(ma, node.c);
    
    // Return the (unchanged) node pointer
    return node;
}
   
// A utility function to do inorder
// traversal of BST
static void inorder(Node root, int s)
{
    if (root != null) 
    {
        inorder(root.left, s);
   
        if (root.c > (s / 2))
            Console.WriteLine(root.key + "\n");
   
        inorder(root.right, s);
    }
}
  
// Driver Code
static public void Main()
{
    int[] a = { 1, 3, 3, 3, 2 };
    int size = a.Length;
    Node root = null;
      
    for(int i = 0; i < size; i++) 
    {
        root = insert(root, a[i]);
    }
      
    // Function call
    if (ma > (size / 2))
        inorder(root, size);
    else
        Console.WriteLine("No majority element\n");
}
}
  
// This code is contributed by rag2127

Javascript

<script>
// javascript program to demonstrate insert 
// operation in binary search tree.
class Node {
    constructor(){
    this.key = 0;
    this.c = 0;
    this.left = null, 
    this.right = null;
    }
  
}
    var ma = 0;
  
    // A utility function to create a
    // new BST node
    function newNode(item)
    {
        var temp = new Node();
        temp.key = item;
        temp.c = 1;
        temp.left = temp.right = null;
        return temp;
    }
  
    // A utility function to insert a new node
    // with given key in BST
    function insert(node , key) {
  
        // If the tree is empty,
        // return a new node
        if (node == null) {
            if (ma == 0)
                ma = 1;
  
            return newNode(key);
        }
  
        // Otherwise, recur down the tree
        if (key < node.key)
            node.left = insert(node.left, key);
        else if (key > node.key)
            node.right = insert(node.right, key);
        else
            node.c++;
  
        // Find the max count
        ma = Math.max(ma, node.c);
  
        // Return the (unchanged) node pointer
        return node;
    }
  
    // A utility function to do inorder
    // traversal of BST
    function inorder(root , s) {
        if (root != null) {
            inorder(root.left, s);
  
            if (root.c > (s / 2))
                document.write(root.key + "\n");
  
            inorder(root.right, s);
        }
    }
  
    // Driver Code
      
        var a = [ 1, 3, 3, 3, 2 ];
        var size = a.length;
        var root = null;
  
        for (i = 0; i < size; i++) {
            root = insert(root, a[i]);
        }
  
        // Function call
        if (ma > (size / 2))
            inorder(root, size);
        else
            document.write("No majority element\n");
  
// This code is contributed by gauravrajput1 
</script>

C++

// C++ Program for finding out
// majority element in an array 
#include <bits/stdc++.h>
using namespace std;
  
/* Function to find the candidate for Majority */
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];
}
  
/* Function to check if the candidate
   occurs more than n/2 times */
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;
}
  
/* Function to print Majority Element */
void printMajority(int a[], int size)
{
    /* Find the candidate for Majority*/
    int cand = findCandidate(a, size);
  
    /* Print the candidate if it is Majority*/
    if (isMajority(a, size, cand))
        cout << " " << cand << " ";
  
    else
        cout << "No Majority Element";
}
  
/* Driver code */
int main()
{
    int a[] = { 1, 3, 3, 1, 2 };
    int size = (sizeof(a)) / sizeof(a[0]);
  
    // Function calling
    printMajority(a, size);
  
    return 0;
}

C

/* Program for finding out majority element in an array */
#include <stdio.h>
#define bool int
  
int findCandidate(int*, int);
bool isMajority(int*, int, int);
  
/* Function to print Majority Element */
void printMajority(int a[], int size)
{
    /* Find the candidate for Majority*/
    int cand = findCandidate(a, size);
  
    /* Print the candidate if it is Majority*/
    if (isMajority(a, size, cand))
        printf(" %d ", cand);
    else
        printf("No Majority Element");
}
  
/* Function to find the candidate for Majority */
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];
}
  
/* Function to check if the candidate occurs more than n/2
 * times */
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;
}
  
/* Driver code */
int main()
{
    int a[] = { 1, 3, 3, 1, 2 };
    int size = (sizeof(a)) / sizeof(a[0]);
    
    // Function call
    printMajority(a, size);
    getchar();
    return 0;
}

Java

/* Program for finding out majority element in an array */
  
class MajorityElement {
    /* Function to print Majority Element */
    void printMajority(int a[], int size)
    {
        /* Find the candidate for Majority*/
        int cand = findCandidate(a, size);
  
        /* Print the candidate if it is Majority*/
        if (isMajority(a, size, cand))
            System.out.println(" " + cand + " ");
        else
            System.out.println("No Majority Element");
    }
  
    /* Function to find the candidate for Majority */
    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];
    }
  
    /* Function to check if the candidate occurs more
       than n/2 times */
    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;
    }
  
    /* Driver code */
    public static void main(String[] args)
    {
        MajorityElement majorelement
            = new MajorityElement();
        int a[] = new int[] { 1, 3, 3, 1, 2 };
        
        // Function call
        int size = a.length;
        majorelement.printMajority(a, size);
    }
}
  
// This code has been contributed by Mayank Jaiswal

Python3

# Program for finding out majority element in an array
  
# Function to find the candidate for Majority
  
  
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]
  
# Function to check if the candidate occurs more than n/2 times
  
  
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
  
# Function to print Majority Element
  
  
def printMajority(A):
    # Find the candidate for Majority
    cand = findCandidate(A)
  
    # Print the candidate if it is Majority
    if isMajority(A, cand) == True:
        print(cand)
    else:
        print("No Majority Element")
  
  
# Driver code
A = [1, 3, 3, 1, 2]
  
# Function call
printMajority(A)

C#

// C# Program for finding out majority element in an array
using System;
  
class GFG {
    /* Function to print Majority Element */
    static void printMajority(int[] a, int size)
    {
        /* Find the candidate for Majority*/
        int cand = findCandidate(a, size);
  
        /* Print the candidate if it is Majority*/
        if (isMajority(a, size, cand))
            Console.Write(" " + cand + " ");
        else
            Console.Write("No Majority Element");
    }
  
    /* Function to find the candidate for Majority */
    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];
    }
  
    // Function to check if the candidate
    // occurs more than n/2 times
    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;
    }
  
    // Driver Code
    public static void Main()
    {
  
        int[] a = { 1, 3, 3, 1, 2 };
        int size = a.Length;
        
        // Function call
        printMajority(a, size);
    }
}
  
// This code is contributed by Sam007

PHP

<?php
// PHP Program for finding out majority 
// element in an array 
  
// Function to find the candidate 
// for Majority 
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];
}
  
// Function to check if the candidate
// occurs more than n/2 times 
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 to print Majority Element 
function printMajority($a, $size)
{
    /* Find the candidate for Majority*/
    $cand = findCandidate($a, $size);
      
    /* Print the candidate if it is Majority*/
    if (isMajority($a, $size, $cand))
        echo " ", $cand, " ";
    else
        echo "No Majority Element";
}
  
// Driver Code
$a = array(1, 3, 3, 1, 2);
$size = sizeof($a);
  
// Function calling
printMajority($a, $size);
  
// This code is contributed by jit_t
?>

Javascript

<script>
    // Javascript Program for finding out majority element in an array
      
    /* Function to print Majority Element */
    function printMajority(a, size)
    {
        /* Find the candidate for Majority*/
        let cand = findCandidate(a, size);
   
        /* Print the candidate if it is Majority*/
        if (isMajority(a, size, cand))
            document.write(" " + cand + " ");
        else
            document.write("No Majority Element");
    }
   
    /* Function to find the candidate for Majority */
    function findCandidate(a, size)
    {
        let maj_index = 0, count = 1;
        let 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];
    }
   
    // Function to check if the candidate
    // occurs more than n/2 times
    function isMajority(a, size, cand)
    {
        let i, count = 0;
        for (i = 0; i < size; i++) {
            if (a[i] == cand)
                count++;
        }
        if (count > parseInt(size / 2, 10))
            return true;
        else
            return false;
    }
      
    let a = [ 1, 3, 3, 1, 2 ];
    let size = a.length;
  
    // Function call
    printMajority(a, size);
  
// This code is contributed by rameshtravel07.
</script>

C++

/* C++ program for finding out majority 
element in an array */
#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;
}
  
// Driver code 
int main() 
{ 
    int arr[] = {2, 2, 2, 2, 5, 5, 2, 3, 3}; 
    int n = sizeof(arr) / sizeof(arr[0]); 
      
    // Function calling 
    findMajority(arr, n); 
  
    return 0; 
} 
  
// This code is contributed by codeMan_d

Java

import java.util.HashMap;
  
/* Program for finding out majority element in an array */
   
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");
    }
  
   
    /* Driver program to test the above functions */
    public static void main(String[] args) 
    {
        int a[] = new int[]{2,2,2,2,5,5,2,3,3};
          
        findMajority(a);
    }
}
// This code is contributed by  karan malhotra

Python3

# Python3 program for finding out majority 
# element in an array 
  
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")
  
# Driver code 
arr = [2, 2, 2, 2, 5, 5, 2, 3, 3] 
n = len(arr)
  
# Function calling 
findMajority(arr, n)
  
# This code is contributed by ankush_953

C#

// C# Program for finding out majority
// element in an array 
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");
}
  
  
// Driver Code
public static void Main(string[] args)
{
    int[] a = new int[]{2, 2, 2, 2, 
                        5, 5, 2, 3, 3};
  
    findMajority(a);
}
}
  
// This code is contributed by Shrikant13

Javascript

<script>
  
// Javascript program for the above approach
  
    function findMajority(arr) 
    {
        let map = new Map();
  
        for(let i = 0; i < arr.length; i++) {
            if (map.has(arr[i])) {
                    let count = map.get(arr[i]) +1;
                    if (count > arr.length /2) {
                        document.write("Majority found :- " + arr[i]);
                        return;
                    } else
                        map.set(arr[i], count);
  
            }
            else
                map.set(arr[i],1);
            }
            document.write(" No Majority element");
    }
      
// Driver Code
    let a = [ 2,2,2,2,5,5,2,3,3 ];
          
    findMajority(a);
  
// This code is contributed by splevel62.
</script>

C++

// C++ program to find Majority 
// element in an array
#include <bits/stdc++.h>
using namespace std;
  
// Function to find Majority element
// in an array
// it returns -1 if there is no majority element
  
int majorityElement(int *arr, int n)
{
    if (n == 1) return arr[0];
      
    int cnt = 1;
      // sort the array, o(nlogn)
    sort(arr, arr + n);
    for (int i = 1; i <= n; i++){
        if (arr[i - 1] == arr[i]){
            cnt++;
        }
        else{
            if (cnt > n / 2){
                return arr[i - 1];
            }
            cnt = 1;
        }
    }
    // if no majority element, return -1
    return -1;
}
  
  
// Driver code
int main()
{
    int arr[] = {1, 1, 2, 1, 3, 5, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
      
    // Function calling 
    cout<<majorityElement(arr, n);
  
    return 0;
}

Java

// Java program to find Majority  
// element in an array 
import java.io.*;
import java.util.*;
  
class GFG{
  
// Function to find Majority element 
// in an array it returns -1 if there
// is no majority element   
public static int majorityElement(int[] arr, int n)
{
      
    // Sort the array in O(nlogn)
    Arrays.sort(arr);
  
    int count = 1, max_ele = -1, 
         temp = arr[0], ele = 0,
            f = 0;
  
    for(int i = 1; i <= n; i++)
    {
          
        // Increases the count if the 
        // same element occurs otherwise
        // starts counting new element
        if (temp == arr[i])
        {
            count++;
        }
        else 
        {
            count = 1;
            temp = arr[i];
        }
  
        // Sets maximum count and stores
        // maximum occurred element so far
        // if maximum count becomes greater
        // than n/2 it breaks out setting
        // the flag
        if (max_ele < count) 
        {
            max_ele = count;
            ele = arr[i];
  
            if (max_ele > (n / 2)) 
            {
                f = 1;
                break;
            }
        }
    }
  
    // Returns maximum occurred element
    // if there is no such element, returns -1
    return (f == 1 ? ele : -1);
}
  
// Driver code 
public static void main(String[] args)
{
    int arr[] = { 1, 1, 2, 1, 3, 5, 1 };
    int n = 7;
  
    System.out.println(majorityElement(arr, n));
}
}
  
// This code is contributed by RohitOberoi

Python3

# Python3 program to find Majority 
# element in an array
  
# Function to find Majority element
# in an array
# it returns -1 if there is no majority element
def majorityElement(arr, n) :
      
    # sort the array in O(nlogn)
    arr.sort()   
    count, max_ele, temp, f = 1, -1, arr[0], 0
    for i in range(1, n) :
          
        # increases the count if the same element occurs
        # otherwise starts counting new element
        if(temp == arr[i]) :
            count += 1
        else :
            count = 1
            temp = arr[i]
              
        # sets maximum count
        # and stores maximum occurred element so far
        # if maximum count becomes greater than n/2
        # it breaks out setting the flag
        if(max_ele < count) :
            max_ele = count
            ele = arr[i]
              
            if(max_ele > (n//2)) :
                f = 1
                break
              
    # returns maximum occurred element
    # if there is no such element, returns -1
    if f == 1 :
        return ele
    else :
        return -1
  
# Driver code
arr = [1, 1, 2, 1, 3, 5, 1]
n = len(arr)
  
# Function calling 
print(majorityElement(arr, n))
  
# This code is contributed by divyeshrabadiya07

C#

// C# program to find Majority  
// element in an array 
using System;
class GFG
{
  
// Function to find Majority element 
// in an array it returns -1 if there
// is no majority element   
public static int majorityElement(int[] arr, int n)
{
      
    // Sort the array in O(nlogn)
    Array.Sort(arr);
  
    int count = 1, max_ele = -1, 
         temp = arr[0], ele = 0,
            f = 0;
  
    for(int i = 1; i < n; i++)
    {
          
        // Increases the count if the 
        // same element occurs otherwise
        // starts counting new element
        if (temp == arr[i])
        {
            count++;
        }
        else 
        {
            count = 1;
            temp = arr[i];
        }
  
        // Sets maximum count and stores
        // maximum occurred element so far
        // if maximum count becomes greater
        // than n/2 it breaks out setting
        // the flag
        if (max_ele < count) 
        {
            max_ele = count;
            ele = arr[i];
  
            if (max_ele > (n / 2)) 
            {
                f = 1;
                break;
            }
        }
    }
  
    // Returns maximum occurred element
    // if there is no such element, returns -1
    return (f == 1 ? ele : -1);
}
  
// Driver code 
public static void Main(String[] args)
{
    int []arr = { 1, 1, 2, 1, 3, 5, 1 };
    int n = 7;
    Console.WriteLine(majorityElement(arr, n));
}
}
  
// This code is contributed by aashish1995 

Javascript

<script>
  
    // Javascript program to find Majority 
    // element in an array
      
    // Function to find Majority element
    // in an array it returns -1 if there
    // is no majority element  
    function majorityElement(arr, n)
    {
  
        // Sort the array in O(nlogn)
        arr.sort(function(a, b){return a - b});
  
        let count = 1, max_ele = -1,
             temp = arr[0], ele = 0,
                f = 0;
  
        for(let i = 1; i < n; i++)
        {
  
            // Increases the count if the
            // same element occurs otherwise
            // starts counting new element
            if (temp == arr[i])
            {
                count++;
            }
            else
            {
                count = 1;
                temp = arr[i];
            }
  
            // Sets maximum count and stores
            // maximum occurred element so far
            // if maximum count becomes greater
            // than n/2 it breaks out setting
            // the flag
            if (max_ele < count)
            {
                max_ele = count;
                ele = arr[i];
  
                if (max_ele > parseInt(n / 2, 10))
                {
                    f = 1;
                    break;
                }
            }
        }
  
        // Returns maximum occurred element
        // if there is no such element, returns -1
        return (f == 1 ? ele : -1);
    }
      
    let arr = [ 1, 1, 2, 1, 3, 5, 1 ];
    let n = 7;
    document.write(majorityElement(arr, n));
  
</script>

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *