Определить наиболее распространенное вхождение в массив

Question

Предположим, у меня есть массив парных чисел, который выглядит следующим образом:

Array[10] = {10, 10, 10, 3, 10, 10, 6, 10, 10, 9, 10}

Мне нужна функция, которая может определить, какой голос MAJORTY находится в массиве, в данном случае «10», потому что эточисло, которое появляется чаще всего ... И, конечно, есть ситуация, когда большинства не существует (где они равны), в таком случае мне нужно выбросить исключение ...

Есть какие-нибудь подсказки?Помимо выполнения некоторых действительно неприятных циклов в массиве (для каждого индекса определите, сколько существует с одним и тем же значением, сохраните счетчик в массиве, а затем просканируйте массив счетчиков на предмет наибольшего числа, и значение в этой позиции является победителем).и т.д ...)

Answer 1

Использование Map<Integer, Integer> должно быть простым как:

int mostFrequent(int... ary) {
    Map<Integer, Integer> m = new HashMap<Integer, Integer>();

    for (int a : ary) {
        Integer freq = m.get(a);
        m.put(a, (freq == null) ? 1 : freq + 1);
    }

    int max = -1;
    int mostFrequent = -1;

    for (Map.Entry<Integer, Integer> e : m.entrySet()) {
        if (e.getValue() > max) {
            mostFrequent = e.getKey();
            max = e.getValue();
        }
    }

    return mostFrequent;
}

Answer 2

Ваша первая проблема заключается в том, что у вас есть «массив двойных чисел», потому что равенство проблематично для данных с плавающей запятой (среди прочего, идентичные числовые значения могут быть представлены различными битовыми шаблонами). Если ваши двойники на самом деле (как в примере) целые числа, используйте int. В противном случае подумайте долго и усердно о том, как определить, какие ценности равны для представления того же голоса.

Что касается определения большинства голосов, используйте Map с «идентификатором голосования» в качестве ключа и количеством голосов в качестве значения - затем в конце выполните итерацию по карте, чтобы найти максимальное значение.

Answer 3

С массивом значений типа double это может быть непросто, поскольку сравнение на равенство довольно сложно. Если вы можете использовать целые числа, вы можете сделать что-то вроде следующего:

    HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    for(int element: Array)
    {
        Integer frequency = map.get(element);
        map.put(element, (frequency != null) ? frequency + 1 : 1);      
    }
    int mostFrequentItem  = 0;
    int[] maxFrequencies  = new int[2];
    maxFrequencies[0]     = Integer.MIN_VALUE;

    for(Entry<Integer, Integer> entry: map.entrySet())
    {
        if(entry.getValue()>= maxFrequencies[0])
        {
            mostFrequentItem  = entry.getKey();
            maxFrequencies[1] = maxFrequencies[0];
            maxFrequencies[0] = entry.getValue();
        }
    }
    if(maxFrequencies[1] == maxFrequencies[0])
        throw new Exception();//insert whatever exception seems appropriate
            return mostFrequentItem  

Это будет иметь производительность O (n), поэтому она должна быть довольно оптимальной для асимптотического поведения производительности. Если ваши двойные значения не являются результатами вычислений, а получены из другого источника, то есть если вы можете быть уверены, что значения, которые в основном одинаковы, будут представлены одинаково, вы можете избежать использования одного и того же метода для двойных чисел, однако я хотел бы все же рекомендуем быть осторожным, что это действительно так.

Редактировать: некоторые улучшения производительности, как предлагается в комментарии, а также поддержка проверки на неоднозначный случай

Answer 4

Сортировка массива сначала с быстрой сортировкой, а затем сканирование и подсчет большинства - O (n ln n). Если диапазон элементов известен заранее, скажем, между {1, k}, то можно использовать сортировку отсчетов, которая будет выполняться в O (n + k).

Как небольшое улучшение, когда вы сканируете отсортированный массив, если вы нашли значение, которое имеет больше чем n / 2 вхождений, вы сделали.

Answer 5

Я только что создал такое красивое и маленькое решение с новой Java 8:

import java.util.Arrays;
import java.util.Collection;
import java.util.HashMap;
import java.util.Map;

public class MostCommonObject {
    public static void main(String[] args) {
        System.out.println(mostCommonObject(new Integer[] { -4, 1, -2, 3, 1, -2, 3, 1 }));
    }

    public static <T> T mostCommonObject(T[] array) {
        return mostCommonObject(Arrays.asList(array));
    }

    public static <T> T mostCommonObject(Collection<T> collection) {
        Map<T, Integer> map = new HashMap<>();
        collection.forEach(t -> map.compute(t, (k, i) -> i == null ? 1 : i + 1));
        return map.entrySet().stream().max((e1, e2) -> Integer.compare(e1.getValue(), e2.getValue())).get().getKey();
    }
}

Answer 6

Как отмечает @Grizzly, двойные значения проблематичны с вычислительной точки зрения. Я бы также предположил, что они не имеют смысла с точки зрения вашей проблемной области; удвоение не имеет смысла при голосовании большинством!

Итак, давайте предположим, что 10, 6 и т. Д. Являются целочисленными идентификаторами того, за что люди голосуют. Предположим также, что вы знаете, что пользователи могут голосовать за любое значение от 0 до 10.

int[] votes = ...
int[] voteCounts = new int[11];  // 11 could be calculated ...
for (int vote : votes) {
    voteCounts[vote]++;
}
int majority = (votes.length + 1) / 2;
for (int i = 0; i < voteCounts.length; i++) {
    if (voteCounts[i] >= majority) {
        return i;  // the winner!
    }
}
throw new NoClearMajorityException(...);

Этот алгоритм O(N) во времени и O(M) в пространстве, где M - самый большой идентификатор. Подвох в том, что он работает (как написано), только если идентификаторы являются целыми числами.

Answer 7

Попробуйте это,

    Integer[] array=new Integer[]{10, 10, 10, 3, 10, 10, 6, 10, 10, 9, 10};

    List<Integer> demoList=new ArrayList<Integer>(Arrays.asList(array));

    Set<Integer> set=new HashSet<Integer>(demoList);

    Map<Integer,Integer> myMap=new HashMap<Integer, Integer>();

    for (Integer integer : set)
    {
        int count=Collections.frequency(demoList, integer);
        myMap.put(count, integer);            
    }

    int maxOccurance=myMap.get(Collections.max(myMap.keySet()));

Answer 8

То, что вы действительно хотите сделать, это подсчитать вхождения определенных предметов в данном наборе. На самом деле это было задано ранее, чем день назад, вы можете посмотреть на этот очень важный вопрос .

Answer 9

Вы можете сделать это: преобразовать ваш массив в список и отсортировать его. Выберите первый индекс и вызовите lastIndexOf (obj) для значения. Делайте это для каждого нового значения, с которым вы столкнетесь, рассчитайте диапазон значения и сохраните результаты самого большого диапазона в переменной.