ReSQL.ru
     
powered by simpleCommunicator - 2.0.49     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Четверговая задачка на поиск
25 сообщений из 55, страница 1 из 3
  1  все
Четверговая задачка на поиск
    #39806268
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Привет. Услышал задачу от коллеги который проводит технические собесы. Заинтересовало.

Дан отсортированный массив целых размером N. После сортировки он - циклически
сдвинут на M шагов. Найти насколько он сдвинут.
...
Рейтинг: 0 / 0
25.04.2019, 14:15
| Ответить | Цитировать | Написать  
Четверговая задачка на поиск
    #39806274
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Я так понимаю не просто найти, а максимально быстро?

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

Это если нет повторов, если есть повторы то только последовательный перебор.
...
Рейтинг: 0 / 0
25.04.2019, 14:29
| Ответить | Цитировать | Написать  
Четверговая задачка на поиск
    #39806284
Roman Mejtes
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Roman Mejtes
Участник
maytonПривет. Услышал задачу от коллеги который проводит технические собесы. Заинтересовало.

Дан отсортированный массив целых размером N. После сортировки он - циклически
сдвинут на M шагов. Найти насколько он сдвинут.
по сути, если массив сдвинут,
Находим значение медианы отрезка массива (на первой итерации всего массива) и проверяем, если её на левом отрезке если начало 1 отрезка меньше значения медианы, значит решение находится в правой части, повторяем это на отрезке в котором находится решение, пока не найдем точку в которой отрезки будет упорядочены. индекс в этой точке будет значением на сколько сместили.
...
Рейтинг: 0 / 0
25.04.2019, 14:35
| Ответить | Цитировать | Написать  
Четверговая задачка на поиск
    #39806303
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Медиана - это o(n).
...
Рейтинг: 0 / 0
25.04.2019, 14:52
| Ответить | Цитировать | Написать  
Четверговая задачка на поиск
    #39806313
Roman Mejtes
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Roman Mejtes
Участник
mayton,

медиана это центр массива и сложность будет логарифмическая O(logn) у данного метода, а не линейная O(n), так как каждый раз мы уменьшаем диапазон поиска в в 2 раза, обычный бинарный поиск.
...
Рейтинг: 0 / 0
25.04.2019, 15:05
| Ответить | Цитировать | Написать  
Четверговая задачка на поиск
    #39806315
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
А сорян. Я думал что имеется в виду медиана как в Фотошопном эффекте median.
...
Рейтинг: 0 / 0
25.04.2019, 15:07
| Ответить | Цитировать | Написать  
Четверговая задачка на поиск
    #39806318
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Код-бы надо. Для пущей убедительности.
...
Рейтинг: 0 / 0
25.04.2019, 15:11
| Ответить | Цитировать | Написать  
Четверговая задачка на поиск
    #39806334
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
maytonПривет. Услышал задачу от коллеги который проводит технические собесы. Заинтересовало.
Дан отсортированный массив целых размером N. После сортировки он - циклически
сдвинут на M шагов. Найти насколько он сдвинут. Для начала, хорошо бы видеть пример, хотя бы до 10-15 чисел.

Во вторых, как можно сравнивать массивы, если дан только один массив - отсортированный?
...
Рейтинг: 0 / 0
25.04.2019, 15:29
| Ответить | Цитировать | Написать  
Четверговая задачка на поиск
    #39806338
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Код: sql
1.
7,8,9,10,1,2,3,4,5,6
...
Рейтинг: 0 / 0
25.04.2019, 15:33
| Ответить | Цитировать | Написать  
Четверговая задачка на поиск
    #39806340
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Так сколько дано массивов?

Представленный массив - не отсортированый.
Его нет в перечне - "дано".
...
Рейтинг: 0 / 0
25.04.2019, 15:37
| Ответить | Цитировать | Написать  
Четверговая задачка на поиск
    #39806345
Roman Mejtes
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Roman Mejtes
Участник
Код: c#
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
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);
}}
...
Рейтинг: 0 / 0
25.04.2019, 15:41
| Ответить | Цитировать | Написать  
Четверговая задачка на поиск
    #39806350
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Roman Mejtes, зацикливается:
Код: c#
1.
2.
		int[] arr = { 7,8,9,10,1,2,3,4,5,6 };
		Console.WriteLine(Find(arr, 0, arr.Length - 1));
...
Рейтинг: 0 / 0
25.04.2019, 15:46
| Ответить | Цитировать | Написать  
Четверговая задачка на поиск
    #39806354
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Roman Mejtes, спасибо.
...
Рейтинг: 0 / 0
25.04.2019, 15:52
| Ответить | Цитировать | Написать  
Четверговая задачка на поиск
    #39806356
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima T, у меня вроде нет. Дотнета нету. Переписал в REPL.
Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
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



Я изначально думал что надо циклический итератор ввести...
...
Рейтинг: 0 / 0
25.04.2019, 15:54
| Ответить | Цитировать | Написать  
Четверговая задачка на поиск
    #39806360
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Можно ли изменить формулировку задачи?

Например,

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

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

Теперь,
имея только новый массив после сдвига на k элементов, как можно определить это число k.
...
Рейтинг: 0 / 0
25.04.2019, 15:58
| Ответить | Цитировать | Написать  
Четверговая задачка на поиск
    #39806365
Roman Mejtes
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Roman Mejtes
Участник
Dima TRoman Mejtes, зацикливается:
Код: c#
1.
2.
		int[] arr = { 7,8,9,10,1,2,3,4,5,6 };
		Console.WriteLine(Find(arr, 0, arr.Length - 1));


у меня не зацикливается
...
Рейтинг: 0 / 0
25.04.2019, 16:03
| Ответить | Цитировать | Написать  
Четверговая задачка на поиск
    #39806368
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Roman MejtesDima TRoman Mejtes, зацикливается:
Код: c#
1.
2.
		int[] arr = { 7,8,9,10,1,2,3,4,5,6 };
		Console.WriteLine(Find(arr, 0, arr.Length - 1));


у меня не зацикливается
Извиняюсь, не зацикливается. Это похоже студия у меня затупила, решил что зациклилось.
...
Рейтинг: 0 / 0
25.04.2019, 16:06
| Ответить | Цитировать | Написать  
Четверговая задачка на поиск
    #39806370
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Некорректно для перевёрнутой сортировки.

Код: sql
1.
2.
3.
4.
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



Мда... за кадром остался вопрос о направлении.
...
Рейтинг: 0 / 0
25.04.2019, 16:08
| Ответить | Цитировать | Написать  
Четверговая задачка на поиск
    #39806374
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonНекорректно для перевёрнутой сортировки.
Больше на меньше замени.

maytonМда... за кадром остался вопрос о направлении.
И о повторах
Код: c#
1.
int[] arr = { 1,1,1,2,1,1,1,1,1,1 };
...
Рейтинг: 0 / 0
25.04.2019, 16:12
| Ответить | Цитировать | Написать  
Четверговая задачка на поиск
    #39806380
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Интересно .. можно ли бросить какой-то ассерт или эксцепшен если этот предикат
дал равенство?

Код: sql
1.
   | if (arr(start) == arr(mid))



Ну и при этом асимптоматику не сломать.
...
Рейтинг: 0 / 0
25.04.2019, 16:20
| Ответить | Цитировать | Написать  
Четверговая задачка на поиск
    #39806383
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Зачем циклы, если задача поставлена так, как описано в 21871816 .

Тогда задача решается с помощью одной формулы!
...
Рейтинг: 0 / 0
25.04.2019, 16:22
| Ответить | Цитировать | Написать  
Четверговая задачка на поиск
    #39806387
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonИнтересно .. можно ли бросить какой-то ассерт или эксцепшен если этот предикат
дал равенство?

Код: sql
1.
   | if (arr(start) == arr(mid))



Ну и при этом асимптоматику не сломать.
Эта проверка не особо замедлит. Рекурсивный вызов намного тяжелее.
...
Рейтинг: 0 / 0
25.04.2019, 16:30
| Ответить | Цитировать | Написать  
Четверговая задачка на поиск
    #39806390
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Соколинский Борис
Участник
Столько всего написали для простейшей задачи.
Число шагов сдвига соответствует первому найденному элементу, который меньше последнего.
Обычный бинарный поиск с корректировкой на равенства.
...
Рейтинг: 0 / 0
25.04.2019, 16:37
| Ответить | Цитировать | Написать  
Четверговая задачка на поиск
    #39806391
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
На таком массиве неправильно сработает
Код: c#
1.
1,2,3
...
Рейтинг: 0 / 0
25.04.2019, 16:38
| Ответить | Цитировать | Написать  
Четверговая задачка на поиск
    #39806394
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Соколинский Борис
Участник
Dima T, правильно.
нулевой элемент будет возвращен, 0 шагов.
...
Рейтинг: 0 / 0
25.04.2019, 16:44
| Ответить | Цитировать | Написать  
25 сообщений из 55, страница 1 из 3
  1  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Четверговая задачка на поиск
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru       Новости, Чат       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=39806365&tid=1339946]:
 0ms
get settings:
 9ms
get forum list:
 16ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 144ms
get topic data:
 10ms
get forum data:
 3ms
get page messages:
 57ms
get tp. blocked users:
 1ms
others: 231ms
total:  479ms
созд. / загр.: 479ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]