Найти наиболее повторяющееся число, используя подход «разделяй и властвуй»?

Question

У меня есть целое число arrayList, которое равно 5, 12, 5, 17, 5, 5, 5, 39 , и я попытался найти наиболее повторяющееся число , и оно работает, чтонапечатает 5 .

Однако я хочу написать это, используя подход «разделяй и властвуй».

Любые советы будут полезны (псевдокод, код Java или любая помощь ...)

public static void main(String[] args) {

        int[] repetitive = { 5, 12, 5, 17, 5, 5, 5, 39 };
        int counter = 1;
        int temp = 0;
        int checker = 1;

        Arrays.sort(repetitive);
        int cont = repetitive[0];

        for (int i = 1; i < repetitive.length; i++) {
            if (repetative[i] == repetitive[i - 1] && cont == repetitive[i]) {
                counter++;
                temp = repetitive[i];

            } else if (repetitive[i] == repetitive[i - 1]) {
                checker++;

                if (checker > counter) {
                    temp = repetitive[i];
                } else if (repetitive[i] != repetitive[i - 1]) {
                    checker = 1;
                }
            }
        }

        System.out.println(temp);
    }

Answer 1

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

В быстрой сортировке вы обычно выбираете элемент x и помещаете элементы <x влево, а остальные справа - и затем рекурсивно сортируете левый и правый массивы.

Здесь вы разбиваете на элементы: left <x, right >x и просто считаете количество элементов равным x, а затем у вас есть левый и правый массивы для обработки.

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

*: Примечание: он будет более эффективным, если на самом деле есть сильно повторяющиеся числа.

Answer 2

не имеет никакого смысла, что вы хотите сделать ...

"Разделяй и властвуй", что, как я считаю, является метафорой для "Binary seach", используется для [как следует из названия] поиска, который не даетсмысл использовать его для подсчета.

Если вы хотите повысить производительность, у вас есть несколько вариантов, не требующих сортировки.

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

Answer 3

«Разделяй и властвуй» здесь неуместно, потому что нет гарантии, что один и тот же результат будет получен из любых 2 подразделов всего списка.Даже если вы сортируете список, потому что вы можете разделить наибольшую группу между подсписками, после чего вы найдете различную наибольшую группу в каждом подсписке и полностью пропустите правильный результат.

Как предполагаетthejavagirl, перечисление списка и подсчет событий, безусловно, самый простой и лучший подход.

Answer 4

этот код подсчитывает вхождения заданного числа в массиве (он не очень эффективен, но с этого стоит начать)

public static void main(String[] args) {
    int[] repetitive = { 5, 12, 5, 17, 12, 12, 5, 39 };
    System.out.println(countOccurences(repetitive));
}

public static Map<Integer, Integer> countOccurences(int[] arr) {
    if (arr.length == 1) {
        Map<Integer, Integer> result = new HashMap<>();
        result.put(arr[0], 1);
        return result;
    } else {

        int to = arr.length / 2;
        Arrays.copyOfRange(arr, 0, to);

        Map<Integer, Integer> left = countOccurences(Arrays.copyOfRange(arr, 0, to));
        Map<Integer, Integer> right = countOccurences(Arrays.copyOfRange(arr, to, arr.length));
        return merge(left, right);
    }
}

static Map<Integer, Integer> merge(Map<Integer, Integer> left, Map<Integer, Integer> right) {
    right.forEach((number, count) -> {
        left.compute(number, (num, c) -> c == null ? count : c + count);
    });
    return left;
}

Answer 5

Почему вы сортируете это в своем примере кода?В этот момент вы можете просто пройтись по нему с самого начала, чтобы найти наиболее повторяющееся.

Предполагая, что вы не не собираетесь сортировать его перед разделением и завоеванием, вы должны принятьразмер списка, находя середину.Обычно для разделения / завоевания используется нечто вроде сортировки слиянием, а вы используете рекурсию.В этом случае вы пытаетесь использовать его для подсчета каждого значения - оно не выглядит наилучшим образом, потому что вам нужно каким-то образом поддерживать состояние того, что имеет наибольшее количество, пока вы выполняете рекурсию (что означает передачу чего-либо).

Что именно является мотивацией здесь - просто пройтись по массиву и вести счет на карте или что-то в этом роде.Это будет O (n) время и O (n) пространство.