В этой статье мы представим различные решения для нахождения k -го по величине элемента в последовательности уникальных чисел. Мы будем использовать массив целых чисел для наших примеров.
Мы также поговорим о средней и наихудшей временной сложности каждого алгоритма.
Теперь давайте рассмотрим несколько возможных решений — одно с использованием простой сортировки и два с использованием алгоритма быстрого выбора, полученного из быстрой сортировки.
В этой статье мы увидим, как найти k -й наименьший элемент в объединении двух отсортированных массивов.
Во-первых, мы определим точную проблему. Во-вторых, мы увидим два неэффективных, но простых решения. В-третьих, мы рассмотрим эффективное решение, основанное на бинарном поиске по двум массивам. Наконец, мы рассмотрим несколько тестов, чтобы убедиться, что наш алгоритм работает.
Мы также увидим фрагменты кода Java для всех частей алгоритма. Для простоты наша реализация будет работать только с целыми числами . Однако описанный алгоритм работает со всеми сопоставимыми типами данных и даже может быть реализован с помощью дженериков.
K -й наименьший элемент в объединении двух отсортированных массивов?В этой статье мы опишем расстояние Левенштейна, также известное как расстояние редактирования. Описываемый здесь алгоритм был разработан русским ученым Владимиром Левенштейном в 1965 году.
Мы предоставим итеративную и рекурсивную реализацию этого алгоритма на Java.
Расстояние Левенштейна — это мера несходства между двумя строками. Математически, учитывая две строки x и y , расстояние измеряет минимальное количество правок символов, необходимых для преобразования x в y .
Односвязный список — это последовательность соединенных узлов, оканчивающаяся нулевой ссылкой. Однако в некоторых сценариях последний узел может указывать на предыдущий узел, что фактически создает цикл.
В большинстве случаев мы хотим иметь возможность обнаруживать и знать об этих циклах; эта статья будет посвящена именно этому — обнаружению и потенциальному удалению циклов.
Давайте теперь рассмотрим пару алгоритмов обнаружения циклов в связанных списках .
В этом руководстве мы объясним, как найти средний элемент связанного списка в Java.
В следующих разделах мы представим основные проблемы и покажем различные подходы к их решению.
Эту проблему можно легко решить, просто отслеживая размер при добавлении новых элементов в список . Если мы знаем размер, мы также знаем, где находится средний элемент, поэтому решение тривиально.
В этом руководстве сравните способы поиска самой длинной подстроки уникальных букв с помощью Java. Например, самая длинная подстрока уникальных букв в «CODINGISAWESOME» — «NGISAWE».
Начнем с наивного подхода. Для начала мы можем проверить каждую подстроку на наличие уникальных символов:
String getUniqueCharacterSubstringBruteForce(String input) {
String output = "";
for (int start = 0; start < input.length(); start++) {
Set<Character> visited = new HashSet<>();
int end = start;
for (; end < input.length(); end++) {
char currChar = input.charAt(end);
if (visited.contains(currChar)) {
break;
} else {
visited.add(currChar);
}
}
if (output.length() < end - start + 1) {
output = input.substring(start, end);
}
}
return output;
}
В этом руководстве мы рассмотрим алгоритм сортировки слиянием и его реализацию в Java .
Сортировка слиянием — один из наиболее эффективных методов сортировки, основанный на парадигме «разделяй и властвуй» .
Сортировка слиянием — это алгоритм «разделяй и властвуй», в котором мы сначала делим проблему на подзадачи. Когда решения для подзадач готовы, мы объединяем их вместе, чтобы получить окончательное решение проблемы.
В этом коротком руководстве мы увидим, как можно эффективно объединить отсортированные массивы с помощью кучи.
Поскольку наша постановка задачи заключается в использовании кучи для объединения массивов, мы будем использовать мини-кучу для решения нашей проблемы. Минимальная куча — это не что иное, как бинарное дерево, в котором значение каждого узла меньше значений его дочерних узлов .
Обычно min-heap реализуется с использованием массива, в котором массив удовлетворяет определенным правилам, когда речь идет о поиске родителя и потомка узла.
