«Разделяй и властвуй». Поиск представителя большинства в массиве

@Kostolom123 · Регистрация: 19.04.2023

Студворк — интернет-сервис помощи студентам

Представителем большинства (majority element) в массиве A[1*....n] называется элемент, равные которому составляют в массиве большинство. Постройте алгоритм, находящий такой элемент (если он есть; если нет, алгоритм может делать что угодно). На элементах массива не задан порядок, поэтому запросы типа «A[i]>A[j]?» запрещены. (Представьте себе, например, массив картинок.) Однако разрешены запросы типа «A[i]=A[j]?», ответы на которые даются за время О(1).

Покажите, как решить такую задачу за время O(n log n). (Подсказка: Для этого разбейте массив на две половины. Если бы вы знали представителей большинства в обеих половинах, могли бы вы быстро найти представителя большинства в исходном массиве? Если да, то можно воспользоваться методом «разделяй и властвуй».)

Пожалуйста помогите с заданием, нужен код на Python. В решении должна быть рекурсия, т.к. нужно сделать с помощью метода «разделяй и властвуй». Заранее спасибо!!!

@eaa · 24.04.2023, 10:12

Сообщение от Kostolom123

равные которому составляют в массиве большинство.

больше n/2?

@Kostolom123 · 24.04.2023, 12:09 **[ТС]**

Просто элемент которого больше всего в массиве, например [1,2,4,5,6,7,1] будет 1

@eaa · 24.04.2023, 13:08

Kostolom123, а если не один такой элемент?

@Kostolom123 · 25.04.2023, 09:45 **[ТС]**

Вернуть первый

@eaa · 25.04.2023, 10:19

тогда это не majority element.

@Kostolom123 · 25.04.2023, 16:26 **[ТС]**

Так как массив я сам задаю, просто задам такой где он только один.

@Red white socks · 26.04.2023, 01:23

Сообщение от Kostolom123

Просто элемент которого больше всего в массиве, например [1,2,4,5,6,7,1] будет 1

Это называется модой. majority element это про другое

@eaa · 26.04.2023, 05:12

majority element:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def foo(arr):
    n = len(arr)
    if n == 1:
        return arr[0], 1
 
    left_arr = arr[:n // 2]
    right_arr = arr[n // 2:]
 
    left_m = foo(left_arr)
    left_count = right_arr.count(left_m[0])
 
    right_m = foo(right_arr)
    right_count = left_arr.count(right_m[0])
 
    if left_count + left_m[1] > n // 2:
        return left_m[0], left_m[1] + left_count
 
    if right_count + right_m[1] > n // 2:
        return right_m[0], right_m[1] + right_count
 
    return None, 0
 
 
print(foo([1, 2, 2, 3, 2, 2, 1, 2]))

Не по теме:

оставлю это здесь, а то лежит уже 2 дня, все равно удалять

Добавлено через 2 минуты
Поиск преобладающего элемента в последовательности

@Catstail · 26.04.2023, 06:47

Сообщение от Kostolom123

решить такую задачу за время O(n log n)

Сообщение от Kostolom123

В решении должна быть рекурсия, т.к. нужно сделать с помощью метода «разделяй и властвуй»

- зачем? Вот решение практически за O(n):

Python
1
2
3
4
5
6
7
8
9
10
11
12
def moda(arr):
    d={}
    amax=-1
    for a in arr:
        if d.get(a) is None:
            d[a]=1
        else:
            d[a]+=1
        if d[a]>amax:
           amax=d[a]
           kmax=a
    return kmax

Добавлено через 1 минуту

Сообщение от Kostolom123

Так как массив я сам задаю

Сообщение от Kostolom123

Представьте себе, например, массив картинок.

-

@Red white socks · 26.04.2023, 09:57

Сообщение от Catstail

- зачем? Вот решение практически за O(n):

Сообщение от Kostolom123

На элементах массива не задан порядок

...

Добавлено через 3 минуты
Catstail, ваше решение подразумевает хэшируемость элементов.

@Catstail · 26.04.2023, 10:02

Red white socks, это да...

Новые блоги и статьи Все статьи Все блоги /
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .

@Kostolom123 0 / 0 / 0 Регистрация: 19.04.2023 Сообщений: 7

	«Разделяй и властвуй». Поиск представителя большинства в массиве 24.04.2023, 07:11. Показов 1389. Ответов 11 Метки нет (Все метки) Представителем большинства (majority element) в массиве A[1*....n] называется элемент, равные которому составляют в массиве большинство. Постройте алгоритм, находящий такой элемент (если он есть; если нет, алгоритм может делать что угодно). На элементах массива не задан порядок, поэтому запросы типа «A[i]>A[j]?» запрещены. (Представьте себе, например, массив картинок.) Однако разрешены запросы типа «A[i]=A[j]?», ответы на которые даются за время О(1). Покажите, как решить такую задачу за время O(n log n). (Подсказка: Для этого разбейте массив на две половины. Если бы вы знали представителей большинства в обеих половинах, могли бы вы быстро найти представителя большинства в исходном массиве? Если да, то можно воспользоваться методом «разделяй и властвуй».) Пожалуйста помогите с заданием, нужен код на Python. В решении должна быть рекурсия, т.к. нужно сделать с помощью метода «разделяй и властвуй». Заранее спасибо!!! 0

@Kostolom123 0 / 0 / 0 Регистрация: 19.04.2023 Сообщений: 7
	24.04.2023, 12:09 [ТС]
	Просто элемент которого больше всего в массиве, например [1,2,4,5,6,7,1] будет 1 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	24.04.2023, 13:08
	Kostolom123, а если не один такой элемент? 0

@Kostolom123 0 / 0 / 0 Регистрация: 19.04.2023 Сообщений: 7
	25.04.2023, 09:45 [ТС]
	Вернуть первый 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	25.04.2023, 10:19
	тогда это не majority element. 0

@Kostolom123 0 / 0 / 0 Регистрация: 19.04.2023 Сообщений: 7
	25.04.2023, 16:26 [ТС]
	Так как массив я сам задаю, просто задам такой где он только один. 0

@Catstail Супер-модератор 38163 / 21098 / 4306 Регистрация: 12.02.2012 Сообщений: 34,686 Записей в блоге: 14
	26.04.2023, 10:02
	Red white socks, это да... 0