Определите наиболее распространенное возникновение в массиве

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

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

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

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

Как указывает @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 - наибольший идентификатор. Загвоздка в том, что он работает (как написано) только в том случае, если идентификаторы являются целыми числами.

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

    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), так что это должно быть довольно оптимальным с точки зрения асимптотической производительности. Если ваши двойники не являются результатом вычислений, а получены из другого источника, то есть если вы можете быть уверены, что значения, которые в основном одинаковы, будут представлены одинаково, вам может сойти с рук тот же метод для двойников, однако я бы по-прежнему рекомендую быть осторожными, чтобы это действительно так.

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

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

Что вы действительно хотите сделать, так это подсчитать количество вхождений определенных элементов в данном наборе. Фактически, раньше об этом задавали менее дня назад, вы можете изучить этот очень важный вопрос .