Может кто-нибудь проверить мой алгоритм для получения режима массива, при этом тай-брейк вообще не работает?

Question

Итак, "diffs" - это массив, такой как [1, 1, 2, 2] или [1, 2, 4, 4]."count" - это, по сути, гистограмма, где значение каждого индекса - это количество раз, которое индекс появляется в "diffs".Таким образом, гистограмма для первого примера будет [0, 2, 2] (размер гистограммы равен 1 + максимум для учета индекса 0).

Я запускаю «count» после того, как он имеетбыл правильно инициализирован, работая в обратном направлении и обновляя режим.Если текущий оцениваемый элемент в «count» равен режиму, то режим устанавливается обратно на -1, что означает отсутствие режима.Это работает для маленьких тестовых случаев, которые у меня есть, но для более крупных я не уверен, что здесь есть ошибка в оценке.

        int mode = -1;
        if (diffs.size() != 0) {
            int[] count = new int[Collections.max(diffs) + 1];
            for (int j = 0; j < diffs.size(); j++) {
                count[diffs.get(j)]++;
            }
            int index = count.length - 1;
            for (int j = count.length - 2; j >= 0; j--) {
                if (count[j] > count[index]) {
                    if (count[j] == count[index]) {
                        mode = -1;
                        break;
                    }
                    index = j;
                    mode = j;
                }
            }
        }

Answer 1

Я не знаю, почему вы устанавливаете режим на -1, если вы нашли два элемента count с одинаковым значением.В описании проблемы, которую я прочитал здесь , говорится, что режим равен

- число, которое появляется в массиве больше раз, чем любое другое число

и

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

Четноеесли вам необходимо вернуть -1 в случае нескольких решений, ваша логика неверна, потому что вы проверяете только count[j] == count[index] внутри if (count[j] > count[index]), поэтому это никогда не будет правдой.Кроме того, даже если вы проверили это за пределами этого условия, прерывание цикла является неправильным, потому что все еще может быть число, которое появляется больше раз.

Возможно, вы хотите что-то вроде этого:

    int mode = -1;
    if (diffs.size() != 0) {
        int[] count = new int[Collections.max(diffs) + 1];
        for (int j = 0; j < diffs.size(); j++) {
            count[diffs.get(j)]++;
        }
        int index = count.length - 1;
        for (int j = count.length - 2; j >= 0; j--) {
            if (count[j] > count[index]) {
                index = j;
                mode = j;
            } else if (count[j] == count[index]) {
                mode = -1;
                // don't break, since we may still find j such that count[j] > count[index]
            }
        }
    }