Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2 3   вперед  Ctrl      все
 Четверговая задачка на поиск  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Привет. Услышал задачу от коллеги который проводит технические собесы. Заинтересовало.

Дан отсортированный массив целых размером N. После сортировки он - циклически
сдвинут на M шагов. Найти насколько он сдвинут.
25 апр 19, 14:15    [21871665]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
Dima T
Member

Откуда:
Сообщений: 13916
Я так понимаю не просто найти, а максимально быстро?

ИМХО что-то типа двоичного поиска: первый сравнить со средним, если первый больше среднего, то берем первую половину, иначе вторую и т.д.

Это если нет повторов, если есть повторы то только последовательный перебор.
25 апр 19, 14:29    [21871677]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
Roman Mejtes
Member

Откуда: г. Пермь
Сообщений: 3429
mayton
Привет. Услышал задачу от коллеги который проводит технические собесы. Заинтересовало.

Дан отсортированный массив целых размером N. После сортировки он - циклически
сдвинут на M шагов. Найти насколько он сдвинут.

по сути, если массив сдвинут,
Находим значение медианы отрезка массива (на первой итерации всего массива) и проверяем, если её на левом отрезке если начало 1 отрезка меньше значения медианы, значит решение находится в правой части, повторяем это на отрезке в котором находится решение, пока не найдем точку в которой отрезки будет упорядочены. индекс в этой точке будет значением на сколько сместили.
25 апр 19, 14:35    [21871694]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Медиана - это o(n).
25 апр 19, 14:52    [21871732]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
Roman Mejtes
Member

Откуда: г. Пермь
Сообщений: 3429
mayton,

медиана это центр массива и сложность будет логарифмическая O(logn) у данного метода, а не линейная O(n), так как каждый раз мы уменьшаем диапазон поиска в в 2 раза, обычный бинарный поиск.
25 апр 19, 15:05    [21871750]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
А сорян. Я думал что имеется в виду медиана как в Фотошопном эффекте median.
25 апр 19, 15:07    [21871754]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Код-бы надо. Для пущей убедительности.
25 апр 19, 15:11    [21871760]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
mayton
Привет. Услышал задачу от коллеги который проводит технические собесы. Заинтересовало.
Дан отсортированный массив целых размером N. После сортировки он - циклически
сдвинут на M шагов. Найти насколько он сдвинут.
Для начала, хорошо бы видеть пример, хотя бы до 10-15 чисел.

Во вторых, как можно сравнивать массивы, если дан только один массив - отсортированный?
25 апр 19, 15:29    [21871781]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
7,8,9,10,1,2,3,4,5,6
25 апр 19, 15:33    [21871785]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Так сколько дано массивов?

Представленный массив - не отсортированый.
Его нет в перечне - "дано".
25 апр 19, 15:37    [21871787]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
Roman Mejtes
Member

Откуда: г. Пермь
Сообщений: 3429
static void Main(string[] args)
{
	var arr = Enumerable.Range(0, 40).ToArray();
	int shift = 11;
	var shiftArr = arr.Skip(arr.Length - shift).Concat(arr.Take(arr.Length - shift)).ToArray();
	Console.WriteLine(string.Join(",", shiftArr));
	Console.WriteLine(Find(shiftArr, 0, shiftArr.Length - 1));
	Console.ReadKey();
}
static int Find(int[] arr, int start, int end)
{
	var mid = start + ((end - start) / 2);
	if (end - start < 2) return mid +1;
	return arr[start] > arr[mid]
		? Find(arr, start, mid)
		: Find(arr, mid, end);
}}
25 апр 19, 15:41    [21871793]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
Dima T
Member

Откуда:
Сообщений: 13916
Roman Mejtes, зацикливается:
		int[] arr = { 7,8,9,10,1,2,3,4,5,6 };
		Console.WriteLine(Find(arr, 0, arr.Length - 1));
25 апр 19, 15:46    [21871799]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Roman Mejtes, спасибо.
25 апр 19, 15:52    [21871804]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Dima T, у меня вроде нет. Дотнета нету. Переписал в REPL.
scala> val arr = Array[Int](7,8,9,10,1,2,3,4,5,6)
arr: Array[Int] = Array(7, 8, 9, 10, 1, 2, 3, 4, 5, 6)

scala>

scala> def find(arr : Array[Int], start : Int, end : Int) : Int = {
     | var mid = start + ((end - start) / 2);
     |
     | if (end - start < 2)
     |                 return mid +1;
     | if (arr(start) > arr(mid))
     | find(arr, start, mid)
     |         else
     | find(arr, mid, end)
     | }
find: (arr: Array[Int], start: Int, end: Int)Int

scala> find(arr, 0, 9)
res0: Int = 4


Я изначально думал что надо циклический итератор ввести...
25 апр 19, 15:54    [21871806]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Можно ли изменить формулировку задачи?

Например,

Имеется N последовательных чисел от 1 до N.
Эти числа помещены в массив N чисел.

С этим массивом провели циклическую сдвижку на k элементов.
Получилось, что теперь первым числом в массиве будет число N-k+1,
а последним числом в массиве будет число N-k.

Теперь,
имея только новый массив после сдвига на k элементов, как можно определить это число k.
25 апр 19, 15:58    [21871816]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
Roman Mejtes
Member

Откуда: г. Пермь
Сообщений: 3429
Dima T
Roman Mejtes, зацикливается:
		int[] arr = { 7,8,9,10,1,2,3,4,5,6 };
		Console.WriteLine(Find(arr, 0, arr.Length - 1));

у меня не зацикливается
25 апр 19, 16:03    [21871824]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
Dima T
Member

Откуда:
Сообщений: 13916
Roman Mejtes
Dima T
Roman Mejtes, зацикливается:
		int[] arr = { 7,8,9,10,1,2,3,4,5,6 };
		Console.WriteLine(Find(arr, 0, arr.Length - 1));

у меня не зацикливается

Извиняюсь, не зацикливается. Это похоже студия у меня затупила, решил что зациклилось.
25 апр 19, 16:06    [21871828]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Некорректно для перевёрнутой сортировки.

val arr = Array[Int](3,2,1,15,14,13,12,11,10,9,8,7,6,5,4)

scala> find(arr, 0, 15 - 1)
res3: Int = 8


Мда... за кадром остался вопрос о направлении.
25 апр 19, 16:08    [21871831]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
Dima T
Member

Откуда:
Сообщений: 13916
mayton
Некорректно для перевёрнутой сортировки.

Больше на меньше замени.

mayton
Мда... за кадром остался вопрос о направлении.

И о повторах
int[] arr = { 1,1,1,2,1,1,1,1,1,1 };
25 апр 19, 16:12    [21871836]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Интересно .. можно ли бросить какой-то ассерт или эксцепшен если этот предикат
дал равенство?

   | if (arr(start) == arr(mid))


Ну и при этом асимптоматику не сломать.
25 апр 19, 16:20    [21871845]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Зачем циклы, если задача поставлена так, как описано в 21871816.

Тогда задача решается с помощью одной формулы!
25 апр 19, 16:22    [21871851]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
Dima T
Member

Откуда:
Сообщений: 13916
mayton
Интересно .. можно ли бросить какой-то ассерт или эксцепшен если этот предикат
дал равенство?

   | if (arr(start) == arr(mid))


Ну и при этом асимптоматику не сломать.

Эта проверка не особо замедлит. Рекурсивный вызов намного тяжелее.
25 апр 19, 16:30    [21871857]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
Соколинский Борис
Member

Откуда: Москва
Сообщений: 10607
Столько всего написали для простейшей задачи.
Число шагов сдвига соответствует первому найденному элементу, который меньше последнего.
Обычный бинарный поиск с корректировкой на равенства.
25 апр 19, 16:37    [21871862]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
Dima T
Member

Откуда:
Сообщений: 13916
На таком массиве неправильно сработает
1,2,3
25 апр 19, 16:38    [21871863]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
Соколинский Борис
Member

Откуда: Москва
Сообщений: 10607
Dima T, правильно.
нулевой элемент будет возвращен, 0 шагов.
25 апр 19, 16:44    [21871870]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2 3   вперед  Ctrl      все
Все форумы / Программирование Ответить