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