В интервью алгоритма интервьюеры всегда любят делать статьи вокруг связанных списков, сортировки, двоичных деревьев и бинарного поиска, и большинство людей могут следовать за профессиональными книгами, чтобы запомнить их. Интервьюер не хочет набирать программиста с хорошими навыками памяти, но не может учиться и применять его. Следовательно, очень важно научиться математически моделировать и анализировать проблемы и использовать разумные алгоритмы или структуры данных для решения проблем.
Вопрос интервью: распечатайте минимальное количество вращающегося массива
Название: Переместите первые несколько элементов массива в конце массива, который мы называем вращением массива. Введите вращение постепенно отсортированного массива и выведите минимальный элемент массива вращения. Например, массив {3, 4, 5, 1, 2} - это вращение массива {1, 2, 3, 4, 5}, а минимальное значение массива составляет 1.
Чтобы достичь этого требования, нам просто нужно пересечь массив, найти наименьшее значение и напрямую выйти из петли. Реализация кода выглядит следующим образом:
public class test08 {public static int getThemin (int nums []) {if (nums == null || nums.length == 0) {throw new runtimeexception ("erron error!"); } int result = nums [0]; for (int i = 0; i <nums.length - 1; i ++) {if (nums [i + 1] <nums [i]) {result = nums [i + 1]; перерыв; }} return result; } public static void main (string [] args) {// Типичный вход, вращение монотонного восходящего массива int [] array1 = {3, 4, 5, 1, 2}; System.out.println (getThemin (Array1)); // есть дубликаты чисел, и наименьшее число, которое представляет собой наименьшее число int [] array2 = {3, 4, 5, 1, 1, 2}; System.out.println (getThemin (Array2)); // есть дублирующие числа, но дубликаты не являются первыми и последними числами int [] array3 = {3, 4, 5, 1, 2, 2}; System.out.println (getThemin (Array3)); // существуют повторяющиеся числа, и дубликаты числа являются первыми и последними числами int [] array4 = {1, 0, 1, 1, 1}; System.out.println (getThemin (Array4)); // монотонное восходящее массив, вращание 0 элементов, то есть монотонное восходящее массив самого int [] array5 = {1, 2, 3, 4, 5}; System.out.println (getThemin (Array5)); // в массиве int [] array6 = {2}; System.out.println (getThemin (Array6)); // числа в массиве являются одинаковыми int [] array7 = {1, 1, 1, 1, 1, 1, 1}; System.out.println (getThemin (Array7)); }}Нет ничего плохого в результатах печати. Однако этот метод, очевидно, не самый лучший. Давайте посмотрим, есть ли способ найти лучший способ справиться с ним.
Упорядочен, все еще нужно искать?
Когда мы найдем эти два ключевых слова, мы неизбежно подумаем о нашем методе бинарного поиска, но многие друзья обязательно будут просить, чтобы наш массив больше не был по -настоящему упорядоченным массивом после вращения, но это похоже на комбинацию из двух постепенных массивов. Мы можем так думать.
Мы можем установить два подписки с низким и высоким, и установить mid = (low + high)/2, и мы, естественно, можем найти массив элементов [Mid] в середине массива. Если средний элемент находится в инкрементном массиве спереди, то он должен быть больше или равен соответствующему элементу низкого подписания. В это время самый маленький элемент в массиве должен быть за элементом. Мы можем указать низкий подход на промежуточный элемент, который может сузить диапазон поисков.
Точно так же, если промежуточный элемент расположен в последующем постепенном субраре, он должен быть меньше или равен элементу, соответствующему высокому индексу. В это время самый маленький элемент в массиве должен быть перед промежуточным элементом. Мы можем обновить высокий индекс в срединном индексе, который также может сузить диапазон поисков. Элементы, соответствующие высоким индексом после перемещения, все еще находятся в последующем постепенном субраре.
Независимо от того, обновляется ли он низким или высоким, наш диапазон поиска будет уменьшен до половины оригинала. Далее мы будем использовать обновленный индекс, чтобы повторить новый раунд поисков. До тех пор, пока два последних подписки не будут смежными, то есть наше конечное состояние.
Я много сказал, и кажется, что я был в беспорядке. С таким же успехом мы могли бы использовать вход в вопрос для моделирования и проверки нашего алгоритма.
Давайте посмотрим, как реализовать эту идею в Java, используя код:
public class test08 {public static int getThemin (int nums []) {if (nums == null || nums.length == 0) {throw new runtimeexception ("erron error!"); } // Если есть только один элемент, непосредственно вернуть if (nums.length == 1) вернуть Nums [0]; int result = nums [0]; int low = 0, high = nums.length - 1; int mid; // Убедитесь, что значение, соответствующее низкому подроду, находится в приращении Subarray слева, а значение, соответствующее высоким, находится в приращении Subarray справа, в то время как (nums [low]> = nums [HIGH]) {// Убедитесь, что конец условия цикла (High - low == 1) {return nums [High]; } // возьмите среднюю позицию mid = (low + high) / 2; // указывает, что средний элемент увеличивается слева, если (nums [mid]> = nums [low]) {low = mid; } else {high = mid; }} return result; } public static void main (string [] args) {// Типичный вход, вращение монотонного восходящего массива int [] array1 = {3, 4, 5, 1, 2}; System.out.println (getThemin (Array1)); // Существуют дублирующиеся числа и наименьшее число, которое просто повторяет числа, int [] array2 = {3, 4, 5, 1, 1, 2}; System.out.println (getThemin (Array2)); // есть дублирующие числа, но дубликаты не являются первыми и последними числами int [] array3 = {3, 4, 5, 1, 2, 2}; System.out.println (getThemin (Array3)); // есть дубликаты чисел, а дубликаты - это именно первое и последнее числа int [] array4 = {1, 0, 1, 1, 1}; System.out.println (getThemin (Array4)); // монотонное восходящее массив, повернуть 0 элементов, то есть монотонное восходящее массив самого int [] array5 = {1, 2, 3, 4, 5}; System.out.println (getThemin (Array5)); // в массиве int [] array6 = {2}; System.out.println (getThemin (Array6)); // числа в массиве являются одинаковыми int [] array7 = {1, 1, 1, 1, 1, 1, 1, 1}; System.out.println (getThemin (Array7)); // Special Я не знаю, как перемещать int [] array8 = {1, 0, 1, 1, 1}; System.out.println (getThemin (Array8)); }}Ранее мы упоминали, что в вращающемся массиве, поскольку несколько чисел в постепенно отсортированном массиве перемещаются за массивом, первое число всегда больше или равно последнему номеру, и есть еще один особый случай, когда 0 элементов перемещаются, то есть сам массив также является его собственным вращающимся массивом. Сама эта ситуация упорядочена, поэтому нам просто нужно вернуть первый элемент, поэтому я сначала назначаю результат [0].
Вышеуказанный код идеален? Мы не соответствовали нашим требованиям через тестовые случаи. Давайте подробно рассмотрим ввод Array8. Давайте впервые проанализируем работу компьютера:
Но мы можем сразу же видеть, что наше минимальное значение составляет не 1, а 0, поэтому, когда массив [низкий], массив [середина] и массив [высокий] одинаково, наша программа не знает, как двигаться. Согласно текущему методу движения, массив [середина] увеличивается слева по умолчанию. Это явно безответственно.
Давайте поправляем код:
public class test08 {public static int getThemin (int nums []) {if (nums == null || nums.length == 0) {throw new runtimeexception ("erron error!"); } // Если есть только один элемент, непосредственно вернуть if (nums.length == 1) вернуть Nums [0]; int result = nums [0]; int low = 0, high = nums.length - 1; int mid = low; // Убедитесь, что значение, соответствующее низкому подроду, находится в приращении Subarray слева, а значение, соответствующее высоким, находится в приращении Subarray справа, в то время как (nums [low]> = nums [HIGH]) {// Убедитесь, что конец условия цикла (High - low == 1) {return nums [High]; } // возьмите среднюю позицию mid = (low + high) / 2; // В особых случаях, когда три значения равны, вам необходимо найти наименьшее значение от начала до конца, если (nums [mid] == nums [low] && nums [mid] == nums [high]) {return midinorder (nums, low, High); } // Указывает, что средний элемент увеличивается слева, если (nums [mid]> = nums [low]) {low = mid; } else {high = mid; }} return result; } / *** Найти минимальное значение в массиве** @param nums массив* @param Start Start Position* @param конечный массив for (int i = start+1; i <= end; i ++) {if (result> nums [i]) result = nums [i]; } return Result; } public static void main (string [] args) {// Типичный вход, вращение монотонного восходящего массива int [] array1 = {3, 4, 5, 1, 2}; System.out.println (getThemin (Array1)); // Существуют дубликаты числа и наименьшее число, которое оказалось наиболее распространенным числом int [] array2 = {3, 4, 5, 1, 1, 2}; System.out.println (getThemin (Array2)); // есть дублирующие числа, но дубликаты не являются первыми и последними числами int [] array3 = {3, 4, 5, 1, 2, 2}; System.out.println (getThemin (Array3)); // есть дубликаты чисел, а дубликаты - это именно первое и последнее числа int [] array4 = {1, 0, 1, 1, 1}; System.out.println (getThemin (Array4)); // монотонное восходящее массив, повернуть 0 элементов, то есть монотонное восходящее массив самого int [] array5 = {1, 2, 3, 4, 5}; System.out.println (getThemin (Array5)); // в массиве int [] array6 = {2}; System.out.println (getThemin (Array6)); // Все числа в массиве являются одинаковыми int [] array7 = {1, 1, 1, 1, 1, 1, 1}; System.out.println (getThemin (Array7)); // Special Я не знаю, как перемещать int [] array8 = {1, 0, 1, 1, 1}; System.out.println (getThemin (Array8)); }}Затем мы вкладываем это с полными тестовыми примерами и проходами теста.
Суммировать
Фактически, этот вопрос имеет много моментов для изучения, но на самом деле он должен изучить гибкое применение бинарного поиска. Многие друзья должны следить за упорядоченным запоминанием бинарных поисков, не изучая идею бинарного поиска, что приведет к размышлениям только о минимальных ценностях циркулярного поиска.
Во время интервью многие друзья сделали заявление о том, что оригинальная экосистема Android в основном инкапсулировала общие алгоритмы и протестовал против этих неэффективных алгоритмов в интервью. Это на самом деле довольно глупо. Мы не стремимся реализовать алгоритмы Rote, но мы стремимся изучить умные идеи в этом. Только постоянно улучшая способность мышления может помочь, чтобы помочь лучше добиться успеха в карьере.
Выше всего содержание этой статьи. Я надеюсь, что это будет полезно для каждого обучения, и я надеюсь, что все будут поддерживать Wulin.com больше.