it-swarm-pt.tech

Encontre o elemento mais popular no array int []

int[] a = new int[10]{1,2,3,4,5,6,7,7,7,7};

como posso escrever um método e retornar 7?

Eu quero mantê-lo nativo sem a ajuda de listas, mapas ou outros ajudantes. Somente matrizes [].

35
SexyMF
public int getPopularElement(int[] a)
{
  int count = 1, tempCount;
  int popular = a[0];
  int temp = 0;
  for (int i = 0; i < (a.length - 1); i++)
  {
    temp = a[i];
    tempCount = 0;
    for (int j = 1; j < a.length; j++)
    {
      if (temp == a[j])
        tempCount++;
    }
    if (tempCount > count)
    {
      popular = temp;
      count = tempCount;
    }
  }
  return popular;
}
34
nIcE cOw

Tente esta resposta. Primeiro, os dados:

int[] a = {1,2,3,4,5,6,7,7,7,7};

Aqui, construímos um mapa contando o número de vezes que cada número aparece:

Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i : a) {
    Integer count = map.get(i);
    map.put(i, count != null ? count+1 : 0);
}

Agora, encontramos o número com a frequência máxima e retornamos:

Integer popular = Collections.max(map.entrySet(),
    new Comparator<Map.Entry<Integer, Integer>>() {
    @Override
    public int compare(Entry<Integer, Integer> o1, Entry<Integer, Integer> o2) {
        return o1.getValue().compareTo(o2.getValue());
    }
}).getKey();

Como você pode ver, o número mais popular é sete:

System.out.println(popular);
> 7

EDIT

Aqui está minha resposta sem usando mapas, listas, etc. e usando apenas matrizes; embora eu esteja classificando a matriz no local. É a complexidade O (n log n), melhor que a solução aceita O (n ^ 2).

public int findPopular(int[] a) {

    if (a == null || a.length == 0)
        return 0;

    Arrays.sort(a);

    int previous = a[0];
    int popular = a[0];
    int count = 1;
    int maxCount = 1;

    for (int i = 1; i < a.length; i++) {
        if (a[i] == previous)
            count++;
        else {
            if (count > maxCount) {
                popular = a[i-1];
                maxCount = count;
            }
            previous = a[i];
            count = 1;
        }
    }

    return count > maxCount ? a[a.length-1] : popular;

}
70
Óscar López
  1. Pegue um mapa para mapear elemento -> contagem
  2. Iterar através da matriz e processar o mapa
  3. Iterar através do mapa e descobrir o popular
8
Jigar Joshi

Assumindo que seu array esteja classificado (como o que você postou) você poderia simplesmente iterar o array e contar o maior segmento de elementos, é algo como o post do @narek.gevorgyan mas sem o array muito grande, e ele usa a mesma quantidade de memória independentemente do tamanho da matriz:

private static int getMostPopularElement(int[] a){
    int counter = 0, curr, maxvalue, maxcounter = -1;
    maxvalue = curr = a[0];

    for (int e : a){
        if (curr == e){
            counter++;
        } else {
            if (counter > maxcounter){
                maxcounter = counter;
                maxvalue = curr;
            }
            counter = 0;
            curr = e;
        }
    }
    if (counter > maxcounter){
        maxvalue = curr;
    }

    return maxvalue;
}


public static void main(String[] args) {
    System.out.println(getMostPopularElement(new int[]{1,2,3,4,5,6,7,7,7,7}));
}

Se a matriz não estiver classificada, classifique-a com Arrays.sort(a);

6
Federico Vera

Este sem mapas:

public class Main {       

    public static void main(String[] args) {
        int[] a = new int[]{ 1, 2, 3, 4, 5, 6, 7, 7, 7, 7 };
        System.out.println(getMostPopularElement(a));        
    }

    private static int getMostPopularElement(int[] a) {             
        int maxElementIndex = getArrayMaximumElementIndex(a); 
        int[] b = new int[a[maxElementIndex] + 1]

        for (int i = 0; i < a.length; i++) {
            ++b[a[i]];
        }

        return getArrayMaximumElementIndex(b);
    }

    private static int getArrayMaximumElementIndex(int[] a) {
        int maxElementIndex = 0;

        for (int i = 1; i < a.length; i++) {
            if (a[i] >= a[maxElementIndex]) {
                maxElementIndex = i;
            }
        }

        return maxElementIndex;
    }      

}

Você só precisa alterar algum código se sua matriz puder ter elementos que sejam < 0. E esse algoritmo é útil quando os itens da matriz não são grandes.

3
narek.gevorgyan

Usando Java 8 Streams  

int data[] = { 1, 5, 7, 4, 6, 2, 0, 1, 3, 2, 2 };
Map<Integer, Long> count = Arrays.stream(data)
    .boxed()
    .collect(Collectors.groupingBy(Function.identity(), counting()));

int max = count.entrySet().stream()
    .max((first, second) -> {
        return (int) (first.getValue() - second.getValue());
    })
    .get().getKey();

System.out.println(max);

Explicação

Nós convertemos a matriz int[] data em Integer Stream in a box. Em seguida, coletamos por groupingBy no elemento e usamos um coletor de contagem secundário para contar após a groupBy.

Finalmente, classificamos o mapa do elemento -> count baseado na contagem novamente usando um comparador de fluxo e lambda.

3
faizan

O valor dos elementos da matriz deve ser menor que o comprimento da matriz para este:

public void findCounts(int[] arr, int n) {
    int i = 0;

    while (i < n) {
        if (arr[i] <= 0) {
            i++;
            continue;
        }

        int elementIndex = arr[i] - 1;

        if (arr[elementIndex] > 0) {
            arr[i] = arr[elementIndex];
            arr[elementIndex] = -1;
        }
        else {
            arr[elementIndex]--;
            arr[i] = 0;
            i++;
        }
    }

    Console.WriteLine("Below are counts of all elements");

    for (int j = 0; j < n; j++) {
        Console.WriteLine(j + 1 + "->" + Math.Abs(arr[j]));
    }
}

A complexidade do tempo disto será O(N) e a complexidade do espaço será O(1).

2
Pavan Tiwari

Se você não quiser usar um mapa, basta seguir estas etapas:

  1. Classifique o array (usando Arrays.sort())
  2. Use uma variável para conter o elemento mais popular (mostPopular), uma variável para manter seu número de ocorrências na matriz (mostPopularCount) e uma variável para conter o número de ocorrências do número atual na iteração (currentCount)
  3. Iterar pelo array. Se o elemento atual for o mesmo que mostPopular, incremente currentCount. Caso contrário, redefina currentCount para 1. Se currentCount for> mostPopularCount, defina mostPopularCount como currentCount e mostPopular como o elemento atual.
2
JB Nizet

Mina Linear O (N)

Usando o mapa para salvar todos os elementos diferentes encontrados na matriz e salvar o número de vezes que ocorreram, basta obter o máximo do mapa.

import Java.util.HashMap;
import Java.util.Map;

public class MosftOftenNumber {

    // for O(N) + map O(1) = O(N) 
    public static int mostOftenNumber(int[] a)
    {
        Map m = new HashMap<Integer,Integer>();
        int max = 0;
        int element = 0;

        for(int i=0; i<a.length; i++){
            //initializing value for the map the value will have the counter of each element
            //first time one new number its found will be initialize with zero 
            if (m.get(a[i]) == null)
                m.put(a[i],0);

            //save each value from the array and increment the count each time its found
            m.put(a[i] , (int)m.get(a[i]) + 1);

            //check the value from each element and comparing with max
            if ((int)m.get(a[i])>max){
                max = (int) m.get(a[i]);
                element = a[i];
            }

        }
        return element;
    }

    public static void main(String args[]) {
//      int[] array = {1,1,2,1,1};
//      int[] array = {2,2,1,2,2};
        int[] array = {2,2,1,3,3,5,5,6,6,7,7,9,9,10,10,10,10,11,12,13,14,15,15,1,15,15,1,15,15};
        System.out.println(mostOftenNumber(array));
    }


}
1
Cesar Chavez

A melhor abordagem será usar o mapa onde a chave será elemento e o valor será a contagem de cada elemento. Junto com isso, mantenha uma matriz de tamanho que irá conter o índice do elemento mais popular. Preencha essa matriz enquanto a própria construção do mapa não precisa fazer uma iteração no mapa novamente.

Abordagem 2: -

Se alguém quiser ir com dois ciclos, aqui está a improvisação da resposta aceita, onde não temos que começar o segundo loop de uma vez

public class TestPopularElements {
    public static int getPopularElement(int[] a) {
        int count = 1, tempCount;
        int popular = a[0];
        int temp = 0;
        for (int i = 0; i < (a.length - 1); i++) {
            temp = a[i];
            tempCount = 0;
            for (int j = i+1; j < a.length; j++) {
                if (temp == a[j])
                    tempCount++;
            }
            if (tempCount > count) {
                popular = temp;
                count = tempCount;
            }
        }
        return popular;
    }

    public static void main(String[] args) {
        int a[] = new int[] {1,2,3,4,5,6,2,7,7,7};

        System.out.println("count is " +getPopularElement(a));
    }

}
1
M Sach
package frequent;

import Java.util.HashMap;
import Java.util.Map;

public class Frequent_number {

    //Find the most frequent integer in an array

    public static void main(String[] args) {
        int arr[]= {1,2,3,4,3,2,2,3,3};

        System.out.println(getFrequent(arr));
        System.out.println(getFrequentBySorting(arr));
    }

    //Using Map , TC: O(n)  SC: O(n)
    static public int getFrequent(int arr[]){
        int ans=0;
        Map<Integer,Integer> m = new HashMap<>();
        for(int i:arr){
            if(m.containsKey(i)){
                m.put(i, m.get(i)+1);
            }else{
                m.put(i, 1);
            }
        }
        int maxVal=0;
        for(Integer in: m.keySet()){
            if(m.get(in)>maxVal){
                ans=in;
                maxVal = m.get(in);
            }
        }
        return ans;
    }

    //Sort the array and then find it TC: O(nlogn) SC: O(1)
    public static int getFrequentBySorting(int arr[]){
        int current=arr[0];
        int ansCount=0;
        int tempCount=0;
        int ans=current;
        for(int i:arr){
            if(i==current){
                tempCount++;
            }
            if(tempCount>ansCount){
                ansCount=tempCount;
                ans=i;
            }
            current=i;
        }
        return ans;
    }

}
1
Praveen Kumar

Parece que você está procurando pelo valor Mode (modo estatístico), dê uma olhada em Apache's Docs para funções estatísticas.

1
Lalith B
import Java.util.Scanner;


public class Mostrepeatednumber
{
    public static void main(String args[])
    {
        int most = 0;
        int temp=0;
        int count=0,tempcount;
        Scanner in=new Scanner(System.in);
        System.out.println("Enter any number");
        int n=in.nextInt();
        int arr[]=new int[n];
        System.out.print("Enter array value:");
        for(int i=0;i<=n-1;i++)
        {
            int n1=in.nextInt();
            arr[i]=n1;
        }
        //!!!!!!!! user input concept closed
        //logic can be started
        for(int j=0;j<=n-1;j++)
        {
        temp=arr[j];
        tempcount=0;
            for(int k=1;k<=n-1;k++)
                {
                if(temp==arr[k])
                    {
                        tempcount++;
                    }   
                        if(count<tempcount)
                            {
                                most=arr[k];
                                    count=tempcount;
                            }
                }

        }
        System.out.println(most);
    }

}
1
Ramesh.k

Assumindo que sua matriz int é classificada, eu faria ... 

int count = 0, occur = 0, high = 0, a;

for (a = 1; a < n.length; a++) {
    if (n[a - 1] == n[a]) {
       count++;
       if (count > occur) {
           occur = count;
           high = n[a];
       }
     } else {
        count = 0;
     }
}
System.out.println("highest occurence = " + high);
1
Dean Spencer

abaixo código pode ser colocado dentro de um método principal

    // TODO Auto-generated method stub
    Integer[] a = { 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 4, 1, 2, 2, 2, 2, 3, 4, 2 };
    List<Integer> list = new ArrayList<Integer>(Arrays.asList(a));
    Set<Integer> set = new HashSet<Integer>(list);
    int highestSeq = 0;
    int seq = 0;
    for (int i : set) {
        int tempCount = 0;
        for (int l : list) {
            if (i == l) {
                tempCount = tempCount + 1;
            }
            if (tempCount > highestSeq) {
                highestSeq = tempCount;
                seq = i;
            }
        }

    }

    System.out.println("highest sequence is " + seq + " repeated for " + highestSeq);
0
Rajkumar
public static void main(String[] args) {

    int[] myArray = {1,5,4,4,22,4,9,4,4,8};
    Map<Integer,Integer> arrayCounts = new HashMap<>();
    Integer popularCount  = 0;
    Integer popularValue = 0;

    for(int i = 0; i < myArray.length; i++) {
        Integer count = arrayCounts.get(myArray[i]);
        if (count == null) {
            count = 0;
        }
        arrayCounts.put(myArray[i], count == 0 ? 1 : ++count);
        if (count > popularCount) {
            popularCount = count;
            popularValue = myArray[i];
        }
    }

    System.out.println(popularValue + " --> " + popularCount);
}
0
jbisa
public class MostFrequentIntegerInAnArray {

    public static void main(String[] args) {
        int[] items = new int[]{2,1,43,1,6,73,5,4,65,1,3,6,1,1};
        System.out.println("Most common item = "+getMostFrequentInt(items));
    }

    //Time Complexity = O(N)
    //Space Complexity = O(N)
    public static int getMostFrequentInt(int[] items){
        Map<Integer, Integer> itemsMap = new HashMap<Integer, Integer>(items.length);
        for(int item : items){
            if(!itemsMap.containsKey(item))
                itemsMap.put(item, 1);
            else
                itemsMap.put(item, itemsMap.get(item)+1);
        }

        int maxCount = Integer.MIN_VALUE;
        for(Entry<Integer, Integer> entry : itemsMap.entrySet()){
            if(entry.getValue() > maxCount)
                maxCount = entry.getValue();
        }
        return maxCount;
    }
}
0
AKh
int largest = 0;
int k = 0;
for (int i = 0; i < n; i++) {
    int count = 1;
    for (int j = i + 1; j < n; j++) {
        if (a[i] == a[j]) {
            count++;
        }
    }
    if (count > largest) {
        k = a[i];
        largest = count;
    }
}

Então, aqui n é o tamanho da matriz, e a[] é a sua matriz.

Primeiro, pegue o primeiro elemento e verifique quantas vezes ele é repetido e aumente o contador (count) para ver quantas vezes ele ocorre. Verifique se esse número máximo de vezes que um número ocorreu até agora se sim, então mude a maior variável (para armazenar o número máximo de repetições) e se você gostaria de armazenar a variável também, você pode fazê-lo em outra variável (aqui k).

Eu sei que este não é o mais rápido, mas definitivamente, a maneira mais fácil de entender

0
MathMan
public static int getMostCommonElement(int[] array) {

    Arrays.sort(array);

    int frequency = 1;
    int biggestFrequency = 1;
    int mostCommonElement = 0;

    for(int i=0; i<array.length-1; i++) {
        frequency = (array[i]==array[i+1]) ? frequency+1 : 1;
        if(frequency>biggestFrequency) {
            biggestFrequency = frequency; 
            mostCommonElement = array[i];
        }
    }

    return mostCommonElement;
}
0
Pawel Seweryn