Алгоритмы | мажоритарный элемент

Я пытаюсь написать алгоритм, возвращающий true, если в массиве существует мажоритарный элемент, и false в противном случае. редактировать: я могу только сказать, равны ли два элемента. это означает, что я не могу использовать ‹ или >, только =. редактировать: решение должно быть в методе «разделяй и властвуй». его время выполнения не должно превышать nlogn, и я написал что-то на java, но я не уверен, правильно ли это и как рассчитать время выполнения. вот что я получил:

public static boolean MajorityBoolean(int[] arr) {
    int c;
    int n = arr.length;
    for (int i = 0; i < n; i = i + 2) {
        System.out.println("*");
        if ((arr[i] == arr[(i + 1)%n]) || ((arr[i] == arr[(i - 1+n)%n]))) {
            c = 0;
            for (int j = 0; j < n; j = j + 1)
                if (arr[j] == arr[i])
                    c = c + 1;
            if (c > n / 2)
                return true;
        }
    }
    return false;
}

element runtime algorithm
person shachar0n    schedule 14.04.2012    source источник
comment
Я добавил тег домашнего задания, так как это, кажется, так. Если я ошибаюсь, пожалуйста, поправьте меня.   -  person amit    schedule 14.04.2012
comment
возможный дубликат Найти основной элемент в массиве   -  person erickson    schedule 14.04.2012
comment
В частности, это является лучшим решением повторяющегося вопроса.   -  person erickson    schedule 14.04.2012

Ответы (3)


arrow_upward
5
arrow_downward

Время выполнения описанного алгоритма O(n^2). Внешний цикл выполняется n/2 раза, таким образом, внутренний счетчик j сбрасывается n/2 раза, и, таким образом, внутренний цикл выполняется всего O(n^2) раз.

Я не уверен, что следую логике вашей идеи, но вот два подхода к ее реализации [в псевдокоде высокого уровня]:

(1) создать гистограмму из данных:

  • создайте Map<Integer,Integer> [ключ — это элемент а значение — количество вхождений]
  • перебрать массив и для каждого элемента подсчитать, сколько раз он появляется
  • повторите гистограмму и найдите, есть ли уникальные максимумы.
  • Если есть - верни true, иначе верни false.

Этот подход имеет среднее значение O(n), если вы используете HashMap как карта.

(2) отсортировать и найти максимальные вхождения:

Это решение O(nlogn) среднее + наихудшее [на самом деле, в зависимости от сортировки - сортировка слияния дает вам O(nlogn) в худшем случае, в то время как быстрая сортировка дает O(n^2) в худшем случае, и оба O(nlogn) в среднем случае ].

РЕДАКТИРОВАТЬ:

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

Кроме того, есть другое решение: использовать алгоритм выбора, чтобы найти медиану, а после ее нахождения проверить если это элемент большинства, и вернуть, если это так. Поскольку алгоритм выбора основан на принципе «разделяй и властвуй», я думаю, что он соответствует вашим потребностям.

person amit    schedule 14.04.2012
comment
во-первых, спасибо за помощь! во-вторых, моя идея заключалась в том, что в каждом массиве, который имеет мажоритарный элемент, должно быть два одинаковых числа друг за другом (учитывая, что массив представляет собой своего рода круг, так что последний элемент близок к первому). это хорошая \ правильная идея? кстати, видимо, мне пришлось написать алгоритм методом «разделяй и властвуй», поэтому мой не очень хорош (также его время выполнения составляет O (n²), что больше, чем ) (nlogn)). - person shachar0n; 14.04.2012
comment
@shachar0n: (1) Я все еще не понимаю логику, почему массив круглый? :\. (2) Я неправильно понял вопрос, я думал, что вы ищете, есть ли уникальные максимумы. Эти два решения по-прежнему соответствуют рассматриваемой проблеме, с модификацией на последнем шаге каждого решения. (3) Описываемый вами вопрос можно решить с помощью алгоритма выбора. Найдите медиану, а затем посмотрите, является ли она мажоритарным элементом. Алгоритм выбора на самом деле является решением «разделяй и властвуй». - person amit; 14.04.2012
comment
(1) я имел в виду, что если в массиве есть мажоритарный элемент, то он должен иметь два одинаковых близких элемента. если массив такой: 1010101 , то последний и первый элементы совпадают - и это то, что я имею в виду, рассматривая массив как круг (используя модуль %). (2)(3) я забыл упомянуть еще одно ограничение: я могу только знать, одинаковы ли два элемента, но я не могу сказать, больше или меньше один, чем другой, то есть я могу использовать только = и не могу использовать : › ‹. - person shachar0n; 14.04.2012

arrow_upward
1
arrow_downward

Элемент большинства в массиве A[] размера n — это элемент, который встречается более n/2 раз.

public static boolean find(int[] arr, int size) { 
int count = 0, i, mElement;
for (i = 0; i < size; i++) {
    if (count == 0)
        mElement = arr[i];
    if (arr[i] == mElement) 
        count++;
    else
        count--;
}
count = 0;
for (i = 0; i < size; i++)
    if (arr[i] == mElement)
        count++;
if (count > size/2)
    return true;
return false;
}
person coder101    schedule 17.02.2015

arrow_upward
0
arrow_downward

Ниже приведено решение O (n) Найти элемент большинства

person MoveFast    schedule 14.04.2012
comment
Это указывает на хорошее решение, но вы должны проголосовать за закрытие повторяющихся вопросов, если можете, или просто прокомментировать вопрос, если не можете. - person erickson; 14.04.2012