Напишите алгоритм, который возвращает элемент мажориты в списке

Question

9. (10 баллов) Напишите алгоритм O (nlogn), чтобы найти элемент большинства из списка элементов. (Предположим, что число элементов является степенью 2). Опять же, единственной операцией, которую вы можете использовать в элементах списка, является сравнение равенства. Подсказка: решить проблему размера п путем решения двух подзадач размера п/2

Это был тест на вопрос разделяй и властвуй, для моего класса алгоритмов. Вот код, который я написал в python 3.5.

def majElement(L): 
    tally = 0 
    if len(L) == 1: 
     return 1 
    for i in range(len(L)): 
     tally = majElement(L[i:len(L)]) + majElement(L[len(L)/2:]) 

     if tally > (len(L)/2): 
      print(L[i]) 

Этот код приводит к переполнению стека. Некоторые из того, как я не добираюсь до основания. Как остановить бесконечные рекурсивные вызовы?

Answer 1

Не уверен в подходе к разделению и завоеванию, но элемент большинства в массиве/списке можно определить в O(nlogn) времени.

Это может быть сделано с помощью binary search tree, используя структуру

struct tree 
{ 
    int element; 
    int count; 
}BST; 

Алгоритм:

1. Вставка элементов в BST один за другим, и если он уже присутствует, то приращение счетчика узла.
2. На любом этапе, если количество узлов становится больше n/2, тогда возвращайтесь.

В худшем случае сложность может быть O(n^2) в случае перекоса BST. Итак, используйте self balancing BST, чтобы обеспечить O(nlogn) раз.

Если вы хотите сделать это с помощью Разделяй и властвуй подход,

Алгоритм:

1. Разделить массив на две части L и R.
2. INT m1 = Большинство (L); int m2 = большинство (R);
3. Если m1 является большинством, верните его.
4. если m2 - это большая часть его перенастроения.
5. В противном случае возвратите элемент «без элемента управления».

Код:

я = 0, J = arr.length;

int majority(int *A, int i, int j) 
{ 
    int m1= majority(A, i, j/2-1); 
    int m2= majority(A, j/2+1, j); 
    int count = 0; 
    for(int i=0; i<j; i++) 
     if(A[i] == m1) 
      count++; 
    if(count > j/2) 
     return m1; 
    count = 0; 
    for(int i=0; i<j; i++) 
     if(A[i] == m2) 
      count++; 
    if(count > j/2) 
     return m2; 
    } 
    return -1; 
} 

Answer 2

Ваша первая проблема заключается в том, что вы только возвращение значение в базовом варианте; в остальное время вы печатаете значение и возвращаете None.

Во-вторых, первый рекурсивный вызов сделан, когда i == 0, что означает L[i:len(L)] такое же, как L, так что вы не acutually уменьшения размера проблемы. По крайней мере, вы хотите for i in range(1, len(L)), но я подозреваю, что вы неправильно декомпилируете проблему в подзадачи. (Вы не должны сделать так много рекурсивных вызовов, как вы предлагаете.)

Answer 3

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

def divideAndConquer(array): #Function to solve by divide and conquer 
    if(len(array)==1): 
     return array[0] 
    middle = len(array)//2 
    left = array[:middle] #First half 
    right = array[middle:] #Second half 
    cLeft = divideAndConquer(left) #candidate for left side 
    cRight = divideAndConquer(right) #candidate for right side 
    if cLeft == cRight: #if both have the same candidate, it is the one 
     return cLeft 
    if array.count(cLeft)>middle: #if not, check in left 
     return cLeft 
    if array.count(cRight)>middle: #else check in right 
     return cRight 
    return "No majority element" #no majority element