Dada una array NxM de enteros que contienen elementos duplicados. La tarea es encontrar el conteo de todos los elementos mayoritarios que ocurren en la array dada, donde los elementos mayoritarios son aquellos cuya frecuencia es mayor o igual a (N*M)/2.
Ejemplos :
Input : mat[] = {{1, 1, 2},
{2, 3, 3},
{4, 3, 3}}
Output : 1
The majority elements is 3 and, its frequency is 4.
Input : mat[] = {{20, 20},
{40, 40}}
Output : 2
Enfoque :
- Atraviese la array y use un mapa en C++ para almacenar la frecuencia de los elementos de la array de modo que la clave del mapa sea el elemento de la array y el valor sea su frecuencia en la array.
- Luego, recorra el mapa para encontrar la frecuencia de elementos con una variable de conteo para contar elementos mayoritarios y verifique si es igual o mayor que (N*M)/2. Si es cierto, aumente el conteo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find count of all
// majority elements in a Matrix
#include <bits/stdc++.h>
using namespace std;
#define N 3 // Rows
#define M 3 // Columns
// Function to find count of all
// majority elements in a Matrix
int majorityInMatrix(int arr[N][M])
{
unordered_map<int, int> mp;
// Store frequency of elements
// in matrix
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
mp[arr[i][j]]++;
}
}
// loop to iterator through map
int countMajority = 0;
for (auto itr = mp.begin(); itr != mp.end(); itr++) {
// check if frequency is greater than
// or equal to (N*M)/2
if (itr->second >= ((N * M) / 2)) {
countMajority++;
}
}
return countMajority;
}
// Driver Code
int main()
{
int mat[N][M] = { { 1, 2, 2 },
{ 1, 3, 2 },
{ 1, 2, 6 } };
cout << majorityInMatrix(mat) << endl;
return 0;
}
Java
// Java program to find count of all
// majority elements in a Matrix
import java.util.*;
class GFG
{
static int N = 3; // Rows
static int M = 3; // Columns
// Function to find count of all
// majority elements in a Matrix
static int majorityInMatrix(int arr[][])
{
HashMap<Integer, Integer> mp =
new HashMap<Integer, Integer>();
// Store frequency of elements
// in matrix
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
if(mp.containsKey(arr[i][j]))
mp.put(arr[i][j], mp.get(arr[i][j]) + 1 );
else
mp.put(arr[i][j], 1);
}
}
// loop to iterator through map
int countMajority = 0;
Iterator<HashMap.Entry<Integer, Integer>> itr =
mp.entrySet().iterator();
while(itr.hasNext())
{
// check if frequency is greater than
// or equal to (N*M)/2
HashMap.Entry<Integer, Integer> entry = itr.next();
if (entry.getValue() >= ((N * M) / 2))
{
countMajority++;
}
}
return countMajority;
}
// Driver Code
public static void main (String[] args)
{
int mat[][] = { { 1, 2, 2 },
{ 1, 3, 2 },
{ 1, 2, 6 } };
System.out.println(majorityInMatrix(mat));
}
}
// This code is contributed by ihritik
Python3
# Python 3 program to find count of all
# majority elements in a Matrix
N = 3 # Rows
M = 3 # Columns
# Function to find count of all
# majority elements in a Matrix
def majorityInMatrix(arr):
# we take length equal to max
# value in array
mp = {i:0 for i in range(7)}
# Store frequency of elements
# in matrix
for i in range(len(arr)):
for j in range(len(arr)):
mp[arr[i][j]] += 1
# loop to iterator through map
countMajority = 0
for key, value in mp.items():
# check if frequency is greater than
# or equal to (N*M)/2
if (value >= (int((N * M) / 2))):
countMajority += 1
return countMajority
# Driver Code
if __name__ == '__main__':
mat = [[1, 2, 2],
[1, 3, 2],
[1, 2, 6]]
print(majorityInMatrix(mat))
# This code is contributed by
# Shashank_Sharma
C#
// C# program to find count of all
// majority elements in a Matrix
using System;
using System.Collections.Generic;
class GFG
{
static int N = 3; // Rows
static int M = 3; // Columns
// Function to find count of all
// majority elements in a Matrix
static int majorityInMatrix(int [ , ]arr)
{
Dictionary<int, int> mp =
new Dictionary<int, int>();
// Store frequency of elements
// in matrix
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
if(mp.ContainsKey(arr[i, j]))
mp[arr[i, j]]++;
else
mp[arr[i, j]] = 1;
}
}
// loop to iterator through map
int countMajority = 0;
Dictionary<int, int>.KeyCollection keyColl =
mp.Keys;
foreach( int i in keyColl)
{
// check if frequency is greater than
// or equal to (N*M)/2
if ( mp[i] >= ((N * M) / 2))
{
countMajority++;
}
}
return countMajority;
}
// Driver Code
public static void Main ()
{
int [, ] mat = { { 1, 2, 2 },
{ 1, 3, 2 },
{ 1, 2, 6 } };
Console.WriteLine(majorityInMatrix(mat));
}
}
// This code is contributed by ihritik
Javascript
<script>
// JavaScript program to find count of all
// majority elements in a Matrix
var N = 3; // Rows
var M = 3; // Columns
// Function to find count of all
// majority elements in a Matrix
function majorityInMatrix(arr)
{
var mp = new Map();
// Store frequency of elements
// in matrix
for (var i = 0; i < N; i++)
{
for (var j = 0; j < M; j++)
{
if(mp.has(arr[i][j]))
{
mp.set(arr[i][j], mp.get(arr[i][j])+1)
}
else
mp.set(arr[i][j], 1);
}
}
// loop to iterator through map
var countMajority = 0;
mp.forEach((value, key) => {
// check if frequency is greater than
// or equal to (N*M)/2
if ( value >= (parseInt((N * M) / 2)))
{
countMajority++;
}
});
return countMajority;
}
// Driver Code
var mat = [ [ 1, 2, 2 ],
[ 1, 3, 2 ],
[ 1, 2, 6 ]];
document.write(majorityInMatrix(mat));
</script>
Producción:
1
Complejidad de tiempo: O(N x M)
Espacio auxiliar: O(NXM)
Optimización adicional:
Podemos usar el algoritmo de votación de Moore para resolver el problema anterior en O(1) espacio extra. Simplemente podemos considerar los elementos de la array como una array unidimensional.