arrays - resueltos - matrices en java netbeans
Encuentra el elemento mayoritario en matriz (17)
El elemento de la mayoría es el elemento que ocurre más de la mitad del tamaño de la matriz.
¿Cómo encontrar el elemento de la mayoría en una matriz en O(n) ?
Ejemplo de entrada:
{2,1,2,3,4,2,1,2,2}
Rendimiento esperado:
2
¿Qué tal un enfoque de muestreo aleatorio? Podría muestrear, decir elementos sqrt (n) y para cada elemento que ocurriera más de sqrt (n) / 4 veces (puede realizarse ingenuamente en el tiempo O (n) y en el espacio O (sqrt (n)), puede verificar si fue un elemento mayoritario en O (n) tiempo.
Este método encuentra la mayoría con alta probabilidad porque el elemento mayoritario se muestrearía al menos sqrt (n) / 2 veces en la expectativa, con una desviación estándar de como mucho n ^ {1/4} / 2.
Otro método de muestreo que es similar a un enfoque que vi en uno de los enlaces duplicados es dibujar dos muestras, y si son iguales verificar que haya encontrado el elemento de la mayoría en el tiempo O (n). El paso de verificación adicional es necesario porque los otros elementos además de la mayoría pueden no ser distintos.
// Supongamos que se nos da una matriz A. // Si tenemos todos los elementos en la matriz dada, cada elemento es menor que K, entonces podemos crear una matriz adicional B con una longitud K + 1.
// Inicialice el valor en cada índice de la matriz con 0. // Luego itere a través de la matriz A dada, para cada valor de matriz A [i], incremente el valor con 1 en el índice correspondiente A [i] en la matriz creada SEGUNDO.
// Después de iterar a través de la matriz A, ahora itere a través de la matriz B y encuentre el valor máximo. Si encuentra un valor mayor que n / 2, regrese ese índice en particular.
// La Complejidad del Tiempo será O (n + K) si K <= n entonces es equivalente a O (n).
// Aquí tenemos una restricción de que todos los elementos de la matriz son O (K). // Suponiendo que cada elemento es menor o igual que 100, en este caso K es 100.
import javax.print.attribute.standard.Finishings;
public class MajorityElement {
private static int maxElement=100;
//Will have all zero values initially
private static int arrB[]=new int[maxElement+1];
static int findMajorityElement(int[] arrA) {
int count = 0, i, majorityElement;
int n=arrA.length;
for (i = 0; i < n; i++) {
arrB[arrA[i]]+=1;
}
int maxElementIndex=1;
for (i = 2; i < arrB.length; i++){
if (arrB[i]>n/2) {
maxElementIndex=i;
break;
}
}
return maxElementIndex;
}`
public static void main(String[] args) {
int arr[]={2,6,3,2,2,3,2,2};
System.out.println(findMajorityElement(arr));
}
}
Así es como lo hago en C ++ usando vectores y multimapas (JSON con teclas repetidas).
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <iterator>
using namespace std;
vector <int> majorityTwoElement(vector <int> nums) {
// declare variables
multimap <int, int> nums_map;
vector <int> ret_vec, nums_unique (nums);
int count = 0;
bool debug = false;
try {
// get vector of unique numbers and sort them
sort(nums_unique.begin(), nums_unique.end());
nums_unique.erase(unique(nums_unique.begin(), nums_unique.end()), nums_unique.end());
// create map of numbers and their count
for(size_t i = 0; i < nums_unique.size(); i++){
// get number
int num = nums_unique.at(i);
if (debug) {
cout << "num = " << num << endl;
}
// get count of number
count = 0; // reset count
for(size_t j = 0; j < nums.size(); j++) {
if (num == nums.at(j)) {
count++;
}
}
// insert number and their count into map (sorted in ascending order by default)
if (debug) {
cout << "num = " << num << "; count = " << count << endl;
}
nums_map.insert(pair<int, int> (count, num));
}
// print map
if (debug) {
for (const auto &p : nums_map) {
cout << "nums_map[" << p.first << "] = " << p.second << endl;
}
}
// create return vector
if (!nums_map.empty()) {
// get data
auto it = prev(nums_map.end(), 1);
auto it1 = prev(nums_map.end(), 2);
int last_key = it->first;
int second_last_key = it1->first;
// handle data
if (last_key == second_last_key) { // tie for repeat count
ret_vec.push_back(it->second);
ret_vec.push_back(it1->second);
} else { // no tie
ret_vec.push_back(it->second);
}
}
} catch(const std::exception& e) {
cerr << "e.what() = " << e.what() << endl;
throw -1;
}
return ret_vec;
}
int main() {
vector <int> nums = {2, 1, 2, 3, 4, 2, 1, 2, 2};
try {
// get vector
vector <int> result = majorityTwoElement(nums);
// print vector
for(size_t i = 0; i < result.size(); i++) {
cout << "result.at(" << i << ") = " << result.at(i) << endl;
}
} catch(int error) {
cerr << "error = " << error << endl;
return -1;
}
return 0;
}
// g++ test.cpp
// ./a.out
El elemento de la mayoría (si existe) también será la mediana. Podemos encontrar la mediana en O (n) y luego verificar que efectivamente sea un elemento de mayoría válido en O (n). Más detalles para el link implementación
Es triste ver que en 5 años nadie ha escrito una explicación adecuada para este problema.
Este es un problema estándar en los algoritmos de transmisión (donde tiene una gran cantidad de datos (potencialmente infinitos)) y tiene que calcular algunas estadísticas de esta secuencia, pasando por esta secuencia una vez.
Es evidente que puede abordarlo con hash o clasificación, pero con un flujo potencialmente infinito, puede quedarse sin memoria. Entonces tienes que hacer algo inteligente aquí.
El elemento de la mayoría es el elemento que ocurre más de la mitad del tamaño de la matriz . Esto significa que el elemento mayoritario ocurre más que todos los demás elementos combinados. Es decir, si cuenta la cantidad de veces que aparece el elemento de la mayoría y resta el número de ocurrencias de todos los demás elementos, obtendrá un número positivo.
Entonces, si cuenta las ocurrencias de algún elemento y resta el número de ocurrencias de todos los otros elementos y obtiene el número 0, entonces su elemento original no puede ser un elemento mayoritario. Esta es la base para un algoritmo correcto:
Declara dos variables, counter y possible_element. Iterar la secuencia, si el contador es 0 - sobrescribe el posible elemento e inicializa el contador, si el número es el mismo elemento posible - aumente el contador, de lo contrario disminuya. Código de Python:
def majority_element(arr):
counter, possible_element = 0, None
for i in arr:
if counter == 0:
possible_element, counter = i, 1
elif i == possible_element:
counter += 1
else:
counter -= 1
return possible_element
Está claro ver que el algoritmo es O(n) con una constante muy pequeña antes de O(n) (como 3). También parece que la complejidad del espacio es O(1) , porque solo tenemos tres variables inicializadas. El problema es que una de estas variables es un contador que potencialmente puede crecer hasta n (cuando la matriz consta de los mismos números). Y para almacenar el número n , necesita el espacio O(log (n)) . Entonces, desde el punto de vista teórico , es el tiempo O(n) y el espacio O(log(n)) . Desde el punto de vista práctico , puede incluir 2 ^ 128 números en una letra larga y esta cantidad de elementos en la matriz es inimaginablemente enorme.
También tenga en cuenta que el algoritmo funciona solo si hay un elemento de mayoría. Si dicho elemento no existe, aún devolverá algún número, lo que seguramente será incorrecto. (es fácil modificar el algoritmo para saber si existe el elemento mayoritario)
Canal de historia: este algoritmo fue inventado en algún momento en 1982 por Boyer, Moore y se lo denominó algoritmo de voto mayoritario de Boyer-Moore.
Esto lo ayudará y si dos elementos se repiten la misma cantidad de veces, si no muestra ninguno.
int findCandidate(int a[], int size)
{
int count,temp=0,i,j, maj;
for (i = 0; i < size; i++) {
count=0;
for(j=i;j<size;j++)
{
if(a[j]==a[i])
count++;
}
if(count>temp)
{
temp=count;
maj=i;
}
else if(count==temp)
{
maj=-1;
}
}
return maj;
}
Gracias por las respuestas anteriores que me inspiraron a conocer el algo de Bob Boyer. :)
Versión genérica de Java: una versión modificada del algoritmo de Boyer
Nota: array de tipo primitivo podría usar wrapper.
import com.sun.deploy.util.ArrayUtil;
import com.sun.tools.javac.util.ArrayUtils;
/**
* Created by yesimroy on 11/6/16.
*/
public class FindTheMajority {
/**
*
* @param array
* @return the value of the majority elements
*/
public static <E> E findTheMajority(E[] array){
E majority =null;
int count =0;
for(int i=0; i<array.length; i++){
if(count==0){
majority = array[i];
}
if(array[i].equals(majority)){
count++;
}else{
count--;
}
}
count = 0;
for(int i=0; i<array.length ; i++){
if(array[i].equals(majority)){
count++;
}
}
if(count > (array.length /2)){
return majority;
}else{
return null;
}
}
public static void main(String[] args){
String[] test_case1 = {"Roy","Roy","Roy","Ane","Dan","Dan","Ane","Ane","Ane","Ane","Ane"};
Integer[] test_case2 = {1,3,2,3,3,3,3,4,5};
System.out.println("test_case1_result:" + findTheMajority(test_case1));
System.out.println("test case1 the number of majority element should greater than" + test_case1.length/2);
System.out.println();
System.out.println("test_case2_result:" + findTheMajority(test_case2));
System.out.println("test case2 the number of majority element should greater than" + test_case2.length/2);
System.out.println();
}
}
Ordenar la matriz dada: O (nlogn).
Si el tamaño de la matriz es 7, entonces el elemento mayoritario aparece al menos en el techo (7/2) = 4 veces en la matriz.
Una vez ordenado el conjunto, significa que si el elemento mayoritario se encuentra por primera vez en la posición i, también se encuentra en la posición i + piso (7/2) (4 ocurrencias).
Ejemplo: matriz dada A - {7,3,2,3,3,6,3}
Ordenar la matriz - {2,3,3,3,3,6,7}
El elemento 3 se encuentra en la posición 1 (índice de matriz a partir de 0.) Si la posición 1 + 3 = 4º elemento también es 3, entonces significa que 3 es el elemento de la mayoría.
si recorremos la matriz desde el principio ...
compara la posición 0 con la posición 3, los diferentes elementos 2 y 3. compara la posición 1 con la posición 4, el mismo elemento. ¡Encontramos nuestro partido mayoritario!
Complejidad - O (n)
Complejidad total del tiempo - O (n).
Para encontrar la mayoría de un elemento en una matriz, puede utilizar el algoritmo de votación mayoritaria de Moore, que es uno de los mejores algoritmos para ello.
Complejidad del tiempo: O(n) or linear time
Complejidad espacial: O(1) or constant space
Lea más en el algoritmo de voto mayoritario de Moore y link
Si se le permite crear una tabla hash y suponer que la búsqueda de la entrada hash es constante, simplemente hash_map cada entrada contra el número de ocurrencias.
Podrías hacer un segundo pase a través de la mesa, obtendrás el que tiene el conteo más alto, pero si sabes de antemano el número de elementos en la tabla, sabrás inmediatamente si tenemos un elemento de mayoría en el primer pase cuando golpeamos el requiere contar en el elemento.
No se puede garantizar, por supuesto, que haya incluso una secuencia de 2 apariciones consecutivas del elemento, por ejemplo, 1010101010101010101 no tiene 1s consecutivos, pero es un elemento de la mayoría.
No se nos dice nada acerca de si hay algún tipo de orden en el tipo de elemento, aunque obviamente debemos poder comparar dos para la igualdad.
Tiempo en)
Espacio: O (n)
Camine por el árbol y cuente la aparición de elementos en una tabla hash.
Tiempo: O (n lg n) o O (n * m) (depende del género utilizado)
espacio: (1)
ordenar la matriz y contar las ocurrencias de los elementos.
La entrevista respuesta correcta: algoritmo de votación de Moore
Tiempo en)
Espacio: O (1)
Recorre la lista para comparar el número actual versus el número de la mejor estimación actual. Si el número es igual al número de la mejor estimación actual, incremente un contador; de lo contrario, disminuya el contador y si el contador llega a cero reemplace el número de la mejor estimación actual con el número actual y establezca el contador en 1. Cuando llegue al final, la corriente La mejor suposición es el número del candidato, recorra la lista de nuevo solo contando las instancias del candidato. Si el recuento final es mayor que n / 2, entonces es el número de la mayoría, de lo contrario no hay uno.
Una versión modificada del algoritmo Boyer,
- 3 pases donde,
- En el primer paso, hacemos una iteración hacia delante de la matriz
- En el segundo pase, hacemos una iteración inversa de la matriz.
- En el tercer pase, obtenga los conteos de los elementos mayoritarios obtenidos en el primer y segundo pase.
Técnicamente un algoritmo de complejidad lineal (O (3n)). Creo que esto debería funcionar para una matriz con un elemento de mayoría que ocurre al menos n / 2 veces.
#include <iostream>
#include <vector>
template <typename DataType>
DataType FindMajorityElement(std::vector<DataType> arr) {
// Modified BOYERS ALGORITHM with forward and reverse passes
// Count will stay positive if there is a majority element
auto GetMajority = [](auto seq_begin, auto seq_end) -> DataType{
int count = 1;
DataType majority = *(seq_begin);
for (auto itr = seq_begin+1; itr != seq_end; ++itr) {
count += (*itr == majority) ? 1 : -1;
if (count <= 0) { // Flip the majority and set the count to zero whenever it falls below zero
majority = *(itr);
count = 0;
}
}
return majority;
};
DataType majority1 = GetMajority(arr.begin(), arr.end());
DataType majority2 = GetMajority(arr.rbegin(), arr.rend());
int maj1_count = 0, maj2_count = 0;
// Check if any of the the majority elements is really the majority
for (const auto& itr: arr) {
maj1_count += majority1 == itr ? 1 : 0;
maj2_count += majority2 == itr ? 1 : 0;
}
if (maj1_count >= arr.size()/2)
return majority1;
if (maj2_count >= arr.size()/2)
return majority2;
// else return -1
return -1;
}
En el algoritmo de Monte-Carlo,
Majority (a,n)
//a[]-array of ''n'' natural numbers
{
j=random(0,1,....,n-1)
/*Selecting the integers at random ranging from 0 to n-1*/
b=a[j];c=0;
for k from 0 to n-1 do
{
if a[k]=b then,
c=c+1;
}
return (c>n/2)
}
Elemento de la mayoría:
Un elemento de la mayoría en una matriz 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).
Encontrar un candidato:
El algoritmo para la primera fase que funciona en O (n) se conoce como el algoritmo de votación de Moore. La idea básica del algoritmo es si cancelamos cada aparición de un elemento e con todos los otros elementos que son diferentes de e, entonces e existirá hasta el final si es un elemento de la mayoría.
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]
El algoritmo anterior recorre cada elemento y mantiene un recuento de un [índice_grande], si el siguiente elemento es el mismo, entonces incrementa el recuento, si el siguiente elemento no es el mismo, entonces disminuye el recuento y si el recuento llega a 0, cambia el índice_grande al actual el elemento y los conjuntos cuentan hasta 1. El algoritmo de primera fase nos da un elemento candidato. En la segunda fase, debemos verificar si el candidato es realmente un elemento mayoritario.
La segunda fase es simple y se puede hacer fácilmente en O (n). Solo debemos verificar si el conteo del elemento candidato es mayor que n / 2.
Lee link para más detalles
int majorityElement(int[] num) {
int major=num[0], count = 1;
for(int i=1; i<num.length;i++){
if(count==0){
count++;
major=num[i];
}
else if(major==num[i]){
count++;
}
else
count--;
}
return major;
}
Complejidad del tiempo O (n)
// returns -1 if there is no element that is the majority element, otherwise that element
// funda :: if there is a majority element in an array, say x, then it is okay to discard
// a part of that array that has no majority element, the remaining array will still have
// x as the majority element
// worst case complexity : O(n)
int findMajorityElement(int* arr, int size) {
int count = 0, i, majorityElement;
for (i = 0; i < size; i++) {
if (count == 0)
majorityElement = arr[i];
if (arr[i] == majorityElement)
count++;
else
count--;
}
count = 0;
for (i = 0; i < size; i++)
if (arr[i] == majorityElement)
count++;
if (count > size/2)
return majorityElement;
return -1;
}
public class MajorityElement
{
public static void main(String[] args)
{
int arr[]={3,4,3,5,3,90,3,3};
for(int i=0;i<arr.length;i++)
{
int count=0;
int j=0;
while(j<arr.length-1)
{
if(i==j)
j=j+1;
if(arr[i]==arr[j])
count++;
j++;
}
if(count>=arr.length/2)
{
System.out.println("majority element"+arr[i]);
break;
}
}
}
}