Красиво и эффективно проанализировать массив

#java

Моя задача в принципе решена, но мне не нравится каким способом.
Есть массив длины > 0 (пусть там будут разные числа int для простоты, не сортированы).
Метод должен вернуть true, если в массиве присутствуют только 2 группы чисел и размеры
этих групп равны либо отличаются на 1. Примеры, возвращающие true: [3,3,5,5] - 2 группы:
3 и 5 - все по 2шт; или [8,8,8,8,2,2,2] - 2 группы: 8-4шт и 2-3шт.
Пример для false: [1,2,3,1,3] - больше чем 2 группы чисел

Без стримов! Остальное можно - стандартные средства джавы.

Пока решение мое такое:

public boolean satisfiedBy(int[] mainCards) {
    Map rankFrequencies = new TreeMap<>();

    for (int rank : mainCards) {
        Integer count = rankFrequencies.get(rank);
        if (count == null)
            count = 0;
        rankFrequencies.put(rank, count + 1);

        // check if there is no more than 2 groups
        if (rankFrequencies.size() > 2)
            return false;
    }

    if (rankFrequencies.size() != 2)
        return false;

    // check if two groups's sizes differs no more than by 1
    Object[] entries = rankFrequencies.entrySet().toArray();
    if (Math.abs(((Map.Entry) entries[0]).getValue() - ((Entry) entries[1]).getValue()) > 1)
        return false;

    return true;
}


Не нравится Object[] entries = rankFrequencies.entrySet().toArray();
и его приведение к нужному типу:

if (Math.abs(((Map.Entry) entries[0]).getValue() - ((Entry) entries[1]).getValue()) > 1)

    

Ответы

Ответ 1

Мне кажется, что наиболее производительный способ выглядит так:


обозначим за array[0] первый элемент массива
находим любой элемент x, не равный array[0]
проверяем, что каждый элемент массива равен либо x, либо array[0]
считаем число вхождений элементов x и array[0]
проверяем, что они различаются не более чем на один




Вариант с одним проходом по массиву (проверка на Ideone):

public static boolean satisfiedBy(int[] array) {
    Integer anotherValue = null;
    int numberOccurrencesOfFirstElement = 0;
    for (int value : array) {
        if (value == array[0]) {
            ++numberOccurrencesOfFirstElement;
        } else if (anotherValue != null && anotherValue != value) {
            return false;
        } else {
            anotherValue = value;
        }
    }
    return anotherValue != null && Math.abs(array.length - numberOccurrencesOfFirstElement
* 2) <= 1;
}


Чуть более читаемый вариант с двумя проходами по массиву (проверка на Ideone):

public static boolean satisfiedBy(int[] array) {
    int element0 = array[0];
    Integer element1 = null;

    for (int value : array)
        if (value != element0)
            element1 = value;
    if (element1 == null)
        return false;

    int count0 = 0;
    int count1 = 0;
    for (int value : array) {
        count0 += value == element0 ? 1 : 0;
        count1 += value == element1 ? 1 : 0;
    }

    return count0 + count1 == array.length && Math.abs(count0 - count1) <= 1;
}


Ответ 2

Давно с джавой не работал, потому эдакий java-псевдокод

Map out = new HashMap<>();

for (int value : array) {
    out.put(value, out.get(value) == null ? 1 : out.get(value) + 1);
    if( out.size() > 2 ) return false;
}

return Math.abs((out.get(out.keySet.toArray[0]) - out.get(out.keySet.toArray[1]))) < 2;


UPD Сначала написал ответ, а потом внимательно вопрос прочитал. :) Как видите, решение
практически полностью совпадает, за исключением некоторых нюансов. Решил не удалять,
потому как вдруг чем-то да поможет код улучшить