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

@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, это да...

Новые блоги и статьи Все статьи Все блоги /
Переходник USB-CAN-GPIO Eddy_Em 20.03.2026 Достаточно давно на работе возникла необходимость в переходнике CAN-USB с гальваноразвязкой, оный и был разработан. Однако, все меня терзала совесть, что аж 48-ногий МК используется так тупо: просто. . .	Оттенки серого Argus19 18.03.2026 Оттенки серого Нашёл в интернете 3 прекрасных модуля: Модуль класса открытия диалога открытия/ сохранения файла на Win32 API; Модуль класса быстрого перекодирования цветного изображения в оттенки. . .	SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++ 8Observer8 17.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-rectangles-sdl3-c. zip finish-rectangles-sdl3-cpp. zip	Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .
[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .	делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .

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

	«Разделяй и властвуй». Поиск представителя большинства в массиве 24.04.2023, 07:11. Показов 1440. Ответов 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 Супер-модератор 38193 / 21126 / 4309 Регистрация: 12.02.2012 Сообщений: 34,732 Записей в блоге: 14
	26.04.2023, 10:02
	Red white socks, это да... 0