Вопросы по теме 'divide-and-conquer'
Передача массива в качестве аргумента в C++
Я пишу функцию сортировки слиянием, и прямо сейчас я просто использую массив тестовых случаев (входных данных нет - пока это статично). Я не знаю, как передать массив в качестве аргумента. Вот мой код прямо сейчас:
//merge sort first attempt...
55020 просмотров
schedule
04.04.2022
Разделяй и властвуй — сравнение всех возможных комбинаций
Эта проблема не дает мне покоя с тех пор, как я над ней работаю. Я пытаюсь найти способ узнать, живут ли определенные люди вместе, основываясь на их парах. Например, мне дан список:
X[] = guy1, guy2, guy3, guy4, guy5
Мне нужен алгоритм D&C,...
1792 просмотров
schedule
24.09.2022
Каково значение рекурсивных вызовов, моделирующих идеальное бинарное дерево?
Я изучаю структуры данных и алгоритмы. В книге, на которую я ссылаюсь (Седжвик), «нахождение максимального элемента» используется для иллюстрации стратегии «разделяй и властвуй». Этот алгоритм делит массив на полпути на две части, находит...
268 просмотров
schedule
27.06.2023
Алгоритм «разделяй и властвуй» для генерации n-битных строк?
Может кто-нибудь рассказать, как генерировать n-битные строки (все возможные комбинации), т.е. считать биты от 0 до 2 ^ n-1 с использованием подхода «разделяй и властвуй».
Я смог сделать это с помощью следующего алгоритма, но пространственная...
1430 просмотров
schedule
22.08.2022
Подсчет количества инверсий в массиве, C ++
Инверсия в массиве a размера n называется парой (i,j) , для которой она содержит i<j и a[i]>a[j] . Я пытаюсь реализовать функцию на C ++, которая подсчитывает количество инверсий в заданном массиве. Я следовал подходу «разделяй и...
2021 просмотров
schedule
17.07.2022
Алгоритм массива «разделяй и властвуй» ++
Я пытаюсь реализовать функцию, которая будет просматривать каждый элемент массива и определять, больше ли этот конкретный элемент одного INT и меньше другого INT. Например:
Return true if Arr[5] is >i && < u
У меня есть это в...
3761 просмотров
schedule
04.03.2023
Алгоритмы «разделяй и властвуй» — вариант бинарного поиска
Это практический вопрос для понимания алгоритмов «разделяй и властвуй».
Вам дан массив из N отсортированных целых чисел. Все элементы различны, за исключением того, что один элемент повторяется дважды. Разработайте алгоритм O (log N), чтобы найти...
421 просмотров
schedule
23.02.2022
Ближайшая пара точек в 3+ измерениях (разделяй и властвуй)
Я изо всех сил пытаюсь понять, как алгоритм «разделяй и властвуй» работает для измерений больше 2, в частности, как найти ближайшую пару точек между двумя подзадачами.
Я знаю, что мне нужно рассматривать только точки на расстоянии d от деления...
3807 просмотров
schedule
16.02.2024
Объясните рекурсию в этом алгоритме?
Я знаю, что этот алгоритм предназначен для поиска мажоритарного элемента любого массива, если он есть. Может ли кто-нибудь объяснить вызовы рекурсии?
if length(A) = 0 then
return null
end if
if length(A) = 1 then
return 1
end if
// "Command...
62 просмотров
schedule
05.11.2022
Ошибка SIGABRT (сигнал 6) при поиске мажоритарного элемента в массиве с использованием функции «разделяй и властвуй»
Я проверил SO и увидел две проблемы, связанные с одной и той же постановкой проблемы. Однако ни один из них не содержал того, что я ищу. Задача состоит в том, чтобы вывести 1, если массив из n элементов содержит элемент, который встречается более...
166 просмотров
schedule
19.04.2024
Как исключить элемент массива в массиве 3 измерения java
У меня возникла проблема с удалением кандидатов в ячейке судоку, я пытался найти кандидатов для заполнения пустых ячеек, как показано ниже.
for (int y = 0; y < 9; y++) {
for (int x = 0; x < 9; x++)
if(game.getNumber(x, y)...
89 просмотров
schedule
18.10.2022
Как исправить этап Conquer этой итеративной реализации быстрой сортировки по примеру Khan Academy?
В образовательных целях я пытаюсь изучить алгоритм быстрой сортировки. Вместо того, чтобы проверять реализацию в Интернете или пытаться реализовать непосредственно из псевдокода в Википедии , Я пробую "жесткий путь".
Я смотрел эту лекцию из CS50...
143 просмотров
schedule
18.02.2023
Временная и пространственная сложность алгоритма «разделяй и властвуй» k-way-merge
Учитывая, что A представляет собой массив из k массивов. Каждый внутренний массив отсортирован и содержит m элементов.
Учитывая этот алгоритм для слияния отсортированных по K массивов, хранящихся в A:
// A is array of sorted arrays...
1296 просмотров
schedule
26.12.2022
Самый длинный общий префикс — анализ сложности подхода «разделяй и властвуй»
Я пытаюсь понять, как была получена сложность времени и пространства для подхода D & C к поиску самого длинного общего префикса из массива строк. Пример: массив строк ["leet", "leetcode", "leeds","le"] и вывод будет "le" Это проблема с leetcode 14...
896 просмотров
schedule
05.02.2024
Большинство элементов изображений JPEG с использованием функции «Разделяй и властвуй»
У вас есть массив A с n изображениями в формате JPEG, некоторые из которых идентичны.
Вы можете проверить, равны ли два объекта, но вы не можете сравнить их каким-либо другим способом, т.е. вы можете проверить A[i] == A[j] и A[i] != A[j], но такие...
46 просмотров
schedule
11.09.2022
Почему разделяй и властвуй быстрее, чем уменьшить, чтобы решить слияние отсортированного списка K
Я использую подход 5: Merge with Divide And Conquer для решения проблемы сортировки слиянием K в leetcode . Алгоритм очень быстрый и занимает около 100 мс. Однако я не понимаю, почему подход reduce требует гораздо более медленного времени...
263 просмотров
schedule
27.12.2022
Сложность следующего алгоритма поиска минимального значения в несортированном массиве
Используя подход «разделяй и властвуй», если мы многократно делим массив на две половины, пока они не уменьшатся до размера двух, после чего мы можем за время O (1) вернуть минимум из двух. Расширяя подход, чтобы объединить два подмассива A и B с их...
2388 просмотров
schedule
05.11.2023
Разделяй и властвуй рекурсивное решение для внесения изменений
Я пытаюсь реализовать программу «разделяй и властвуй», которая при наличии набора монет c = {c0, c1,...,cn} и суммы A находит, сколько различных способов можно заплатить A, а также как много раз функция рекурсивно выполнялась.
Моя мысль состоит в...
285 просмотров
schedule
14.05.2022
Элемент большинства, использующий разделяй и властвуй
Я хочу найти элемент большинства из списка, используя алгоритм «разделяй и властвуй».
Я видел этот код на Leetcode с этим решением:
class Solution:
def majorityElement(self, nums, lo=0, hi=None):
def majority_element_rec(lo, hi):
#...
206 просмотров
schedule
23.05.2022
Всегда ли «Разделяй и властвуй» работает лучше?
В настоящее время я тестирую некоторые алгоритмы «разделяй и властвуй» в сравнении с их обычными реализациями. Я новичок в этом, и я не уверен, всегда ли я должен получать лучшую производительность при использовании разделяй и властвуй. Например, я...
99 просмотров
schedule
19.08.2022