Все эти задачки мне почему-то напомнили как один парень у нас в универе сдавал зачёты, подходил к одному спрашивал что спрашивает препод, потом к другому, потом к третьему, в общем так он перебирал абсолютно все варианты что спрашивал препод по конкретной лабе и потом сдавал её. Но стоило преподу однажды перед ним поставить новую задачу, которую он никогда ни у одного студента не спрашивал, как всё хорошее и закончилось.
@@andrewmurruvyov4359 Это я к тому, что нафига вообще рассматривать методы решения задач, ну вот знаете вы как решить эту конкретную задачу в гугл на миллион долларов в год, а дай вам новую как всё хорошее и закончится, и нифига вы её уже не решите, потому что вы как этот парень из универа, вместо того чтобы учиться решать самому, тупо спрашивал у всех и перебирал все возможные варианты, а сам решать так и не научился, надо учится самому решать, а не смотреть на решения других людей и думать что теперь я мега умный и сам смогу решить такую задачу. Как говорится: всё просто когда знаешь как, а если не знаешь, то и таблица умножения кажется мега сложной задачей.
@@andrewmurruvyov4359 как правило такие говноработники которые не умеют работать, а умеют устраиваться, потом долго не работают. потому что потом уже НАДО РАБОТАТЬ, а не сдавать 🤣🤣🤣
А что забавнее, что эти задачи мало кто решает так изящно сам по себе, фактически все учат только принципы и шаблоны, которых не так много. Это большой труд, но как это помогает определить хорошего программиста - вопрос :)
@@Hello-g5b3p, всё зависит от того, для решения каких задач нужен программист. Хороший программист для одних, ужасен для других. Скажем, задача та же, только у в распоряжении лишь три регистра и только один из них имеет ёмкость достаточную для указания на ячейку в матрице, при этом никто не лимитирует алгоритм по времени. Практическое применение: микроконтроллер без ОЗУ, все прочие регистры заняты другими данными всей микропрограммы, а её частью является алгоритм, микроконтроллер может 16 MIPS, а управляет дверным замком (то есть, даже если на сравнение уйдёт 30000 выполненных операций для матрицы 6*7, то это всего лишь задержка 0,001875 секунды, что человек в принципе не в состоянии заметить, да и замок открываться в следствии наличия инерции засова всё равно будет открываться дольше). И написать надо всё естественно на ассемблере. Так что, да, очень актуальен вопрос - как определить хорошего программиста?
we can do 2 binary searches, firstly we can go through the rows and find the right row(if the target is greater than the midRow's last element then startRow=midRow+1), and then do a binary search only for that row, in that case we will have O(logn + logm).
@@dmitryzhuk220 Не скажу что быстрее чем в видео нельзя решить, я как раз сейчас думаю над этим, но если элемент m[i][j] < k, то можно сказать лишь что наш элемент находится НЕ выше и левее, а иначе НЕ ниже и правее, то есть мы можем отрезать прямоугольную подматрицу в которой элемент не находится, но не выделить онную
@@mrseeker9075по идее матрицу можно нарезать на 4 меньшие матрицы (относительно ключевого элемента в центре) а потом рекурсивно повторять алгоритм до размера в 1 элемент и просто проверять этот 1 элемент на равенство. Единственное что есть риск переполнения стека на огромных матрицах
Сразу подумал что нужно идти по диагонали. Вот только не объяснил почему с правого верхнего угла пошли. Без разницы с какого угла идти, числом может быть как ближе к наименьшему так и ближе к на большему, соответственно если искомое число например 2 то поиск будет максимально долгим. Решение этой задачи можно немного оптимизировать так: mid = (max + min) / 2 Если n < mid то идём по диагонали с верхнего левого угла, если n > mid то с правого верхнего угла. Дальше действуем без изменений.
Я в целом решил таким же образом, только начинал с левого верхнего угла и не считаю, что этот метод менее эффективен. Просто в данном случае, у нас 4 столбца с числами меньше 14 и 2 с числами больше 14,но возможна и обратная ситуация
При k=5 выгоднее начинать с левого верхнего угла, а при k=24 выгоднее начинать с правого нижнего угла. Поэтому начинают с середины, как в обычном бинарном поиске: либо с правого верхнего угла, либо с левого нижнего угла.
@@РоманБондарь-м3е Мне показалось правильными начинать с правого нижнего. Ну то есть если бы мне дали 5 минут подумать, то мой вариант был бы таким. Хоть и не оптимальный.
Левый верхний менее эффективен, нужно откатываться назад на 1 столбец упираясь в большее в следующем. Двигаться будем не по прямой (приближенной к прямой "траектории"), а "зигзагами". Представьте, что это не просто матрица, а пиксели на дисплее и каждая ваша выборка данных из матрицы закрашивает пиксель, увидите траекторию.
@@smarthedgehog3185 "бери меньший и ищи в этой строке" Если я правильно понял, то из примера на доске, вы найдете стоблец (11, 12, 16...) Но в нем нет 14)
Вот честно поставил на паузу на 2:24: я бы использовал что-то типа волнового алгоритма. Начинаем с элемента (0;0) и смотрим всех его соседей (по 8 направлениям, где это возможно), если среди соседей нет числа К, то перемещаемся на позицию максимального числа; в нашем случае (1;1) со значением 5 и так до тех пор пока у текущего элемента не будет соседа со значением 5, ну плюс ещё условие выхода из цикла со значением false, если вдруг текущее значение стало больше К. Теперь по честному нажимаю play и смотрю дальше 😀
эх, не удалось решить самому так элегантно, не додумался до возможности начать справа сверху, только левый верх и правый низ рассматривал) отличный разбор!
❤ хоть у тебя и мало разборов, но они очень информативные, может будет хотя бы по 3 задачи в неделю - контент мега полезный, особенно для джунов. В Яндексе дают похожие.
Спасибо за задачу. Кажется, что если на каждой строке или столбце, по которым мы передвигались из верхнего правого угла до 14, сделать бинарный поиск, то можно получить что-то около logN + logM
Тоже возникла такая мысль. По сути, он для каждой строки ищет число, которое было бы меньше N, чтобы по этому столбцу далее найти число, котоое было бы больше N. И снова по строке, по столбцу и т.д.
оптимальное решение быстрее. основная логика та же, но начинать надо не с левого верхнего угла, а с "середины"матрицы. правда надо будет немного заморочиться с обработкой вариантов. зато средняя скорость решения примерно в 2 раза выше получится.
Во-первых - 2 раза быстрее не получится, тк мы теряем возможность двигаться по диагонали в одном направлении - тк если число, которое мы ищем, например, больше "серединного" - то оно может быть как правее, так и ниже. А во-вторых O(n/2+m/2) = O(n+m). Так что усложняя себе жизнь, вы не получаете никаких бонусов.
Примерно такое же решение с поиском таргетного числа вокруг текущего в голову пришло, Только мне пришло в голову стартовой точкой задать не верхний правый угол а середину (по аналогии с бинарным поиском). В результате при прогоне данной матрицы от 0 до 36, разница в шагах внутри цикла составила 214 (твое решение со стартовой точкой в углу) против 127 со стартовой точкой в центре. Центр находил абсолютно банально через Math.floor(arr.length / 2) и Math.floor((arr[0].length - 1) / 2); Вроде как шустрее почти в два раза получается :) Спасибо за задачу!
Тоже самое подумал, про центр сразу. Да и к тому же можно внести ещё одну оптимизацию, тем более если известен характер чисел (насколько случайные числа были отсортированы и какая случайность использовалась) Можно брать не крайний верхний угол, а относительный порядковый номер диагонали беря во внимание крайние значения таблицы. К примеру видим что таблица начинается с 1 и заканчивается 36. А надо найти число 14, тогда делим искомое число, на разницу начального числа таблицы и конечного. Получаем 0.4. Далее умножаем 0.4 на размерность таблицы и далее округляем числа. И получаем координату оптимального старта поиска, чем линейнее распределение, тем точнее будет координата старта.
@@The14Some1 Понятное дело не обещал. Просто так алгоритм будет работать быстрее на больших размерностях и при разных функциях распределениях и незначительно медленнее на малых размерностях и не линейных функциях распределения
Круто. А главное красиво.Лично мне первое пришедшее в голову решение было: 1) берем среднее по номеру число в средней строке. Если такого нет - ближайшее (к примеру 7 если всего 15. Или 8. Без разницы). Мысленно мы разделили по строке и столбцу на 4 секции. Если К меньше числа, то мы отсекаем все большие числа по строке и столбцу. И повторяем это всё. В программировании я совершенно не разбираюсь, думала с точки зрения математики скорее.
была детская задачка отгадать число от 1 до 1024 за 10 попыток. тебе говорят больше или меньше задуманного то что ты назвал. лень проверять, но думаю такой способ более эффективен чем предложенный.
с левого верхнего угла на каждом шаге выбирать элемент правее и элемент ниже. сравнивать эти 2 соседних элемента и двигаться по пути наименьшего из выбранных пока не пересечемся с искомым или не превысим его значение. подход аналогичен описанному но только более понятен
Решил так же! Почти ) Понял, что надо идти лесенкой. Сперва в 1-й строке найти число большее к, сдвинуться к предыдущему индексу в строке, увеличить индекс по вертикали. Все, как вы описали. Единственное отличие - я пошел слева направо. Вам хорошо, вы видите все значения в массиве, а программа их не видит. Первое же левое число в строке может быть к! Или другое, достаточно "левое" число. Нет никаких преимуществ у больших чисел справа перед меньшими числами слева - к может стоять ближе как к левому, так и к правому краю. Неплохо было бы еще двоичный поиск min числа > к в 1-й строке добавить! Потому, как можно почти всю строку пропахать в поисках такого числа, а оно окажется ближе к краю, противоположной началу поиска. Спасибо за задачу! Понравилась.
Друг, есть более быстрый способ. Первое, проверяем число в ячейке 1,1 и m,n убеждаемся что число К в середине и переборку начинаем с середины в таком случае получаем O((m+n)/2). Можно конечно и не проверять начало с концом тогда, тогда, если брать худший сценарий будет еще быстрее, однако если брать лучший сценарий то можно и без переборки сказать что нет числа в матрице
Что есть середина матрицы 2х10? Мы должны курсор поставить в 1,5? А, может, в 2,6? Но мысль красивая с проверкой 1,1 и m,n. Если искомое число не в матрице (меньше наименьшего элемента или больше наибольшего), то выполним за 1 или 2 операции)
@@АлександрКраснов-н5ж Допустим дана матрица 100х200, надо найти число К=14. Вы начали с середины, там число 50. Все что вы теперь знаете, это то, что правую нижнюю часть можно отбросить. Но куда теперь вам дальше двигаться? Число К может быть в любой из трёх оставшихся областей. Причем оно может быть как левее середины, так и правее, как ниже середины, так и выше.
@@SayXaNow а если дальше опять повторить ход в середину оставшейся области? то есть по сути всегда делим на 2 и сверяем....и того вместо 7 будет 5 ходов
Ваше решение занимает, на данном примере, 7 шагов. Мое 5-6. Именно с угла, откуда, по Вашим словам, нет смысла начинать. А именно. Смотрим первую цифру. Если =14, то тру. Если больше - фолз. Если меньше - делаем шаг n+1 и m+1. Т.е. по диагонали. Те же условия, за исключением того, что если больше 14, то проверяем 2 числа по краям диагонали. Итого, в конкретном примере, Ваше решение идет по числам 16-15-11-12-16-9-14, выдавая "тру" с седьмой проверки. Мое идет по 1-5-9-17-16-14 (или 1-5-9-17-14) выдавая результат с 5-6 раза. Всего, максимум шагов, для проверки всех чисел матрицы, у Вас может быть 10 (кратчайший прямой путь от верхнего правого до нижнего левого угла). В моем случае - 7. 5 на диагональ - 2 на проверку рядом с диагональю. (в данном примере, после числа 30 проверяется 36 и 27, если они были бы меньше или равны 14). Отсюда вывод - Ваше решение не оптимально. Могу кодом, если так проще воспринимать.
но моя идея состояла в том чтобы идти исключительно по диагонали допустим слева направо... тобишь arr[0][0] далее arr[1][1] и так далее на перекрестии будет цифра либо отсекающая сектор точно меньше либо точно больше и потом нужно будет только вернуться от этой цифры вверх или вниз
проблема идти по диагонали в том, что ты не знаешь куда поворачивать как только найдешь значение больше искомого, а значит придется запоминать в какой момент ты повернул и в какую сторону, если же идти по вертикали/горизонтали и влево-вправо/вверх-вниз, то ничего запоминать не придется
Видимо мы думаем по-разному. Двигаемся с 0,0 по главной диагонали пока значение ячейки не станет больше искомого (17) Далее просто проверяем все значения строки, столбца (17).
Самое быстрое решение, которое я смог найти, вот такое: Находим центральную строку, бинарным поиском делим её на две части - до и после искомого числа. Проводим от этой точки мысленную горизонтальную и вертикальную линию, тем самым разделив таблицу на 4 части. Левый верхний угол выкидываем, там все числа меньше искомого. Правый нижний тоже выкидываем, там все числа больше. А в левом нижнем и в правом верхнем углах запускаем этот алгоритм рекурсивно. Получаем логарифмическое время посика. P.S. видос ещё не смотрел.
Отличное решение, масштабируемое! Тоже думаю надо отталкиваться от центра в этой задаче, путь из одного конца матрицы в другой может быть слишком долгим
То, что сразу полезло в голову: 1) Проходимся по каждому элементу первой строки и ищём первое число, которое будет больше k 2) Делаем то же, но для первого столбца 3) Ограничиваем область поиска k найденными ранее элементами массива 4) Используем любой поиск. В худшем случае ограничение у нас займёт O(n+m), а поиск - O(n1 * m1), где n1 и m1 - элементы-ограничители (при прохождении по каждому элементу).
Можно еще ограничивать область если найти число которое меньше k (не рассматривать левую верхнюю область). И тогда такое решение может быть даже быстрее чем то которое рассказали.
В худшем случае (k>18), а это почти половина возможных k, размер матрицы не уменьшается. Но ваше решение натолкнуло меня на другое. Нужно, чтобы опытный алгоритмист проверил, может я тоже не прав. Решение: 1) в первой строке доходим до последнего =к. Зачеркиваем для себя все, что ниже. 3) в уже ограниченой матрице идем по первому столбцу до последнего =к. Зачеркиваем для себя, все что левее. Проходки логично делать бинарным поиском. Если я все правильно понимаю по крайней мере в этой таблице за эти 4 этапа находим наше число. Если таблица больше надо пример, чтобы понять что дальше делать, но так мы гарантированно сильно уменьшаем зону поиска. Получается 2log(m) + 2log(n)
@@OstapP Если нашли число меньшее k, то нам не подходят все числа которые (одновременно) левее и выше этого найденного числа (там все числа меньше k). Аналогично с числом большим k. Т.о любое число неравное k ограничивает нашу область поиска.
Жаль только, что на собесах не обеспокоены качеством кода, а только задачками. Каждый раз, когда приходится обновлять сервисы гугла: firebase, admob, playgames - молишься, как бы хуже не стало. Ошибки без исправлений годами висят. Примерчик: подключаешь любой самый ссаный рекламный провайдер и ANR в норме, подключаешь admob и ANR в космос летит.
Странно, меня вот в одном из собеседований на трейни отшили именно по причине, что я не пользовался модулями и недостаточно явно поделил логику и вывод. А в другом отшили за то, что я это сделал, а они выбрали кандидатов, предпочёвших более простые решения.
Кажется, что задачу можно решить за О(log(m+n)). Надо в упорядоченной линии, которая похожа на диагональ матрицы( длина m+n) найти наибольшее число меньше искомого( это называется правосторонний поиск ). Следующее число будет больше искомого. Вместе они образуют матрицу 2х2. Осталось проверить оставшиеся два элемента матрицы на совпадение с искомым.
Хороший результат, линейный алгоритм оптимизированный для двумерного случая. Для еще более быстрого поиска можно бинарный поиском найти строку и далее найти столбец также бинарным поиском. Сложность будет еще меньше.
В принципе всё правильно. Но исходя из того-же бинарного принципа начинать надо не с краёв а с середины. То есть с числа 16. Ну и идти придётся не в одну сторону, а в зависимости от сравнения. В данном конкретном случае дойдём до 14 за 2 хода 🙂
левый нижний и правый верхний углы для линейного алгоритма - это две единственные ключевые точки из которых за одно сравнение существует только один единственный путь движения. для любой другой стартовой точки матрицы таких пути уже два. но нормальные люди в упорядоченных последовательностях ищут бинарным поиском по строкам, начиная с граней
@@SayXaNow Я вот как думаю: - В принципе даже условие задачи не совсем строгое - что такое самый быстрый (или оптимальный) алгоритм поиска? - В общем случае я вижу как минимум 2 интерпретации. - 1 - Минимальное количество шагов в среднем. - 2 - Минимизировать количество шагов для самого плохого случая. Очевидно, что алгиритмы получатся разные. Для второго алгоритма, особенно для большого количества рядов (например 1 000 000 000) не оптимально двигаться последовательно по лесенке. Надо целый массив разбивать на кучки (на 2, а лучше на 3), проверять граничные условия прыгая из одной в другую и убирать целые кучки (суб массивы). Когда осталась кучка небольшого размера (надо считать какого), тогда уже можно идти по лесенке от верхнего правого угла... Ну может я и не прав???
@@Proezdom-zx2tl Ну задача с подвохом. я всегда топил и топлю за бинарный алгоритм. В матрице случайных упорядоченных значений размером 2500х10000 он показывает скорость нахождения любого элемента в среднем за 67 шагов. Казалось бы - фантастика, ну что за лохи вообще топят за этот линейный аутизм, ведь налицо логарифмическая скорость. Но надо учесть один нюанс. могут попадаться квадратные блоки данных, в которых числа расположены особым образом и полностью удовлетворяют условию задачи (правее всегда числа больше, снизу от любого числа тоже всегда больше), но для которых не существует в принципе алгоритма быстрее, чем линейный ступеньками. И если вдруг в моей матрице мне попался именно такой блок размером 2500х2500 то максимально неудачный расклад для бинарного поиска составит 50000 шагов и примерно 15000 в среднем для любого числа такого блока. Не трудно посчитать что неторопливый линейный тут покажет лучший результат. И т.к. никаким способом нельзя быстро проверить попался нам такой блок или нет, я бы не рискнул использовать быструю бинарку для слишком больших квадратных матриц. Сначала бы убедился что большая сторона M превосходит меньшую N хотя бы в 5 раз. А если ярко выраженная прямоугольная длинная типа 1000х17000 - тут даже обсуждать нечего - только бинарный поиск. Страшилка конечно это все, да и вероятность мала нарваться на такое, поэтому юзаю бинарки и не заморачиваюсь. Но как минимум надо помнить теперь об этом. Такие вот любопытные подробности всплыли, когда занимался тестами.
а можно ведь и за 2*log(N). В начале бинарный поиск по колонке, проверяем верхнюю и нижнюю колонку. Если два последних числа в верхней и нижней колонке больше искомого идем внизу, если оба меньше вверх. Если в верхней колонке число меньше искомого, а в нижней нет - мы нашли нужную колонку за O(n) А дальше уже стандартный бинарный поиск по столбцу
не знаю почему, но думаю это решение можно назвать одним из оптимальных. Как вариант можно использовать информацию, что за числа находятся на вершинах это матрицы и основываясь на этом принимать решение откуда начинать двигаться
а вообще можно совместить и сделать тройное решение тобишь находить быстро точку входа допустим цифру 17 потом от нее идти влево вниз и одновременно вверх вправо
Кажется, что ходить до границы матрицы из верхнего правого угла может быть расточительно. При какой-нибудь матрице 1e12 x 1e12 (абстрактная большая цифра). Может стоить добавить в код условие про то, что если k < верхнего левого угла || k > нижнего правого угла, то искать нет смысла (false).
В этой матрице выполняется условие, что все элементы левее и выше меньше или равно текущего элемента, а все элементы правее и ниже - больше текущего элемента. Об элементах левее и ниже и правее и выше ничего однозначно сказать нельзя. Среди них могут встречаться меньшие, равные или большие. Поэтому матрицу надо проходить до конца.
@@dmytrozazulin1858 , по-моему вы либо не так интерпретируете мое сообщение, или не так интерпретируете условие. Простой вопрос: Если в правом нижнем углу матрицы значение, равное 500, может ли в матрице быть значение, например, 501? Если да, составьте пример такой матрицы, я посмотрю, как вы это сделаете, не нарушая условий
@@dmytrozazulin1858 , ну это по сути внесение изменений в алгоритм поиска, но не в алгоритм скана матрицы самой. Если у нас матрица триллион x триллион, есть ли смысл долго по ней ходить, если за константное время можно сразу сделать вывод, что ходить по ней нет смысла. Я это хотел донести, если что. В алгоритме, представленном в видео, уже есть предварительные проверки перед сканированием матрицы, мой поинт был лишь в том, что возможно стоит расширить эти проверки.
можно еще бинарным поиском попрбовать. Делим на 4 квадранта, смотрим в каждом из них левое верхнее и правое нижнее, и сравниваем с искомым. Например, если первоначальным разбиением взять за центр 16, то правый нижний квадрант можно отсечь и левый верхний квадрант можно отсечь. Далее рекурсивно ищем в правом верхнем и в левом нижнем.
@@denisgluk431 нет. Даже если в 3 подматрицы придется заглядывать, оценка будет логарифмической, так как на каждой итерации пространство поиска сужается на множитель, а не на константу. А в более чем 3 подматрицы смотреть гарантированно будет не нужно.
А если взять 1 число - середину матрицы, и смотреть если число меньше 14 смотреть правое и снизу; дальше выбирать то, которое больше 14 и меньше второго? И двигаться таким полукрестом. Как скорость оценить?
Изменено: не работает( Мне кажется есть не менее эффективный способ, хотя хз насколько он будет лучше в коде. 1) делим количество строк на 2 (округляя) и начинаем с этой цифры. (В данном случае 3) 2) если число меньше то идем вверх, больше вниз. (В данном случае вниз, доходя до 10) 3) теперь также делим уже столбцы (и округляем, в данном случае это не нужно, но при изменении условий пригодилось бы), то есть мы на числе 14. 4) Если число меньше то идем в лево, если больше в право. Но в данной ситуации это не пригодилось. В чем же преимущество этого метода? Если считать именно колличество ходов их будет максимум 7. (Если ищем число 36) В случае описанном в видео 10. (Если ищем число 18)
@@desmosmech7037 Это просто крайний случай для бинарного поиска по строкам. Ничего не меняет. Бинарный поиск это метод сходящихся интервалов. Ты просто ускоряешь их сходимость деля на два длину. В Численных методах этот метод ещё называли поиском льва в пустыне :) Грубо говоря там можно и площади делить отрезком. Т.е. сначала делить матрицу по столбцам потом по строкам в зависимости от того какая часть длиннее.
Можно ещё быстрее, если начинать проверку с любой цифры в центре матрицы. Тогда ты найдёшь ответ в среднем В ДВА РАЗА БЫСТРЕЕ, чем ты показал. Это вааще очевидно.
Первая (и последняя идея) 1)Проверить первый столбец и первую строку на наличие цифр больше 14 и отсечь их. В нашем случае матрица станет 4 на 4. 2) проверить в обратном порядке последний столбец и строку новой матрицы (4 на 4) и отсечь все, что меньше 14. (Осталось 2 на 2) 3) оставшуюся маленькую матрицу просто перебрать А потом я досмотрел видео и в очередной раз понял, что я тупой
Вау! Красивое решение! Сразу придумал бинпоиск. И еще бинпоиском по первому и последнему столбцу можно убрать часть строк, в которых точно нет искомого числа. Но это асимптотику не улучшит.
а если число столбцов очень большее? а К находится ближе в первой половине или еще ближе к левой части? ( не будет ли разумно сравнить число К с количеством столбцов так как данные в матрице натуральные числа и начать с самого максимального в котором столбце она может быть?)
Ну, прописать 4 алгоритма для старта с каждого угла. И выбирать угол в зависимости от этого числа. Но это лишний гемор) ТЕм более что условие задачи поставило конкретное число, а не рандомное
Сильно сложный алгоритм поиска, и не факт, что он применим для разных вариантов этой матрицы, мне кажется, что по этой причине тут и повторяются числа.
А мне показалось, что надо начинать с середины матрицы по типу двоичного поиска: 16 > 14, поэтому примерно четверть матрицы вправо и вниз от 16-ти не подходит. И т.д....
Задача понятна. Возникает вопрос, а почему идём с правого верхнего угла? Чисто логически можно идти с любого угла. Принцип одинаковый. С другой стороны если вопрос стоит в скорости то можно попробовать идти с центра. Это если требуется среднюю скорость поиска уменьшить.
Принципы разные. Для получения удобной формулы нам нужно идти либо с левого-нижнего, либо с правого-верхнего угла - чтобы иметь однозначное решение если текущее число больше или меньше необходимого.
Как я (не программист) решал примерно такую задачу, не зная наверняка широко известных в узких кругах методов решения подобных задач. Думаю, что такой метод имеет название, но я назвал его для себя методом сжимающихся границ. Исходно, считаем, что искомое находится между 1-й (нижняя граница) и последней (верхняя граница) строкой. проверяем на средней (понятно, что округляем, промежуток нечётный). После проверки средняя строка становится или новый нижней границей или новой верхней и интервал уменьшается вдвое. И так, пока верхняя не станет равной нижней. После этого аналогичный поиск в этой строке, но уже по столбцам. Единственное, мне нужен был поиск в массиве из сотен или тысяч строк и столбцов и я делил интервал не пополам, а на 10 частей и, хотя сравнений было больше, сужал интервал в 10 раз. Думаю, что программисты знают более стандартные и быстрый способы, но мой работал, хотя я писал его на VisualBasic (самоучка). Основной проблемой было, что значения в матрице были дробные и нужно было найти значение "примерно" равное. Пришлось придумывать "примерное" сравнение (с заданной точностью), т.к просто округление могло происходить в разные стороны и последняя цифра отличалась. Но это уже другая история)))))
Можно сделать функцию, которая ищет в упорядоченном массиве заданное число, если не находит, то возвращает следующее по убыванию и его индекс. Тогда алгоритм выглядел бы так: делаем поиск в первой строчке [1..16] находим 11 и его индекс 3 делаем поиск в первом столбце [1..18] находим 10 и индекс 3 останется сделать поиск заданного числа в подстолбце (0, 3)-(3, 3) это числа [11, 12, 16, 17] и в подстрочке (3, 0)-(3, 3), где значения [10, 13, 14, 17] сложность не умею точно считать, но вроде должно быть в среднем 1.5*O(log n) + 1.5*O(log m), о том что можно идти змейкой как-то не догадался)
я придумал решение только за m * log n. Ищу в каждой строке нужное число методом бинарного поиска. В общем-то самое элементарное решение если нужна временная сложность меньше, чем O(n * m) function isK(arr, num) { for (let i = 0; i < arr.length; i++) { let left = 0; let right = arr[i].length - 1; let center;
while (left num) { right = center - 1; } else { left = center + 1; } } } return false; }
Бинарным поиском можно, только их не 1, а 4 нужно написать (за 10 минут можно не успеть). Пусть сначала область поиска - весь массив. 1. Находим (бин. поиск) последний элемент в первой строке, не превосходящий искомого. Выкидываем область правее данного элемента (там все элементы больше искомого). 2. Находим (бин. поиск) последний элемент в первом столбце, не превосходящий искомого. Выкидываем область ниже данного элемента (там все элементы больше искомого). 3. Находим (опять бин. поиск) первый элемент в последней строке, который больше или равен искомому. Выкидываем область левее данного элемента (там все меньше). 4. Находим (и опять бин. поиск) первый элемент в последнем столбце, который больше или равен искомому. Выкидываем область выше данного элемента (и там все меньше). Повторяем для полученной меньшей области, пока она не схлопнется до 0 или 1 элемента.
поставив на паузу мне в голову пришло такое решение - идем сначала по первому столбцу и находим строку первый элемент которой БОЛЬШЕ искомого числа , найдя ее мы получаем строку в которой ищем (это предыдущая строка). Далее идем по первой строке и ищем столбец, первый элемент которого БОЛЬШЕ искомого значения, так мы получаем предельный номер столбца (он будет равен найденному минус один), до которого делать поиск в строке найденной на первом шаге. Далее идем по строке определенной на шаге один до столбца найденного на шаге 2 и ищем нужное значение
Если на то пошло, то оптимальней сначала найти угол с наиболее близким числом и плясать от него. Код увеличится, зато выпоняться будет быстрее всего для любого числа.
Правый верхний угол можно найти дихотомией, что даст еще меньшую оценку, О(logn + m). Далее идти по "диогоналям" можно не поэлементно а также дихотомией, что в общем случае даст O(log n + log m). Такое конечно за 15 минут не написать, но устно я бы обязательно упомянул про более оптимальные пути поиска.
А зачем нужно первое отсечение? Есть инсайдерская информация, что мы так большую часть матрицы выкинем? Дихотомия по диагоналям мне то же пришла в голову, но сложность такого алгоритма останется прежней - O(n+m). Однако ожидаемая сложность такого подхода будет меньше, но не O(log(n)+log(m)), а O(log(n)*log(m)).
@@АнтонДанильченко-е6н, первым отсечением мы сразу уменьшим прямоугольник с m * n до (m-k) * n. В примере на видео - верхний правый элемент с которого можно начинать это 11 (первый элемент меньше 14). Но да, точно, согласен, в случае дихатомаии , оценка будет O(log(m) * log(n)).
Совершено все верно. Использование дихотомии есть самый эффективный метод. Сам решил дихотомией через диагонали, не так сложно как кажется на первый взгляд, ибо алгоритм дихотомии всем известен наизусть. Диагональная дихотомия - эффективность log(n)^2, где n - наименьшая сторона. Но алгоритм требует рекурсии, т.к. матрица разбивается на каждом шаге на две валидных области, в которых снова применяем алгоритм. Чередующаяся дихотомия по строкам и столбцам - эффективность log(n)*log(m). Код чуть длиннее, но пишется по факту быстрее и понимается лучше. Не требует рекурсии - что огромнейший плюс. Окончательный вариант из видео - это фиаско. Применять последовательный поиск в упорядоченной последовательности - это провал собеседования.
@@kostyajan Если по диагоналям отсекать оказывается эффективней, то зачем нужен первый шаг, который может отрезать неопределённое кол-во столбцов (в том числе и 0)?
1. вариант смотрим строку начальное и конечное значение так понимаем есть ли в этой строке искомое число, далее когда поняли какая строка тем же бинарным поиском воспользуемся что бы найти число. 2. Взять самое левое число, самое правое, и так же самое нижнее левое, самое нижнее правое. На основе этого прикинуть в каком примерно месте распологается искомое число. На основе этого нужен хитрый рандомизатор который из получившегося множества будет выдавать индекс, и там уже сомтреть подходит ли этот индекс. Ну либо в получившемся регионе использовать вариант 1
Написал на Java. Принцип работы - идем по столбцам, перебираем числа в строках каждого столбца. Когда доходим до числа, которое больше K, - переходим на следующий столбец. Если за это время мы находим число, равное K, то возвращаем истину. Если за все итерации не находим число, равное K, то возвращаем ложь. Сам код: public class Main { public static boolean check(int[][] arr, int k) { int column = 0, m = arr[0].length; while(column < m) { for(int[] ints : arr) { if(ints[column] > k) break; if(ints[column] == k) return true; } column += 1; } return false; } public static void main(String[] args) { int k = 14; int[][] arr = { {1, 4, 7, 11, 15, 16}, {2, 5, 8, 12, 19, 22}, {3, 6, 9, 16, 22, 24}, {10, 13, 14, 17, 24, 27}, {18, 21, 23, 26, 30, 36} }; if(check(arr, k)) System.out.println("The given matrix contains the number " + k + "."); else System.out.println("The given matrix doesn't contain the number " + k + "."); } }
Лять... То чувство, когда начал расписывать решение в комментариях, написал, смотришь видос - а тут то же самое решение, и если оставить коммент, то ты будешь выглядеть дурачком каким-то, который зачем-то переписал из видоса, а если удалить, то спрашивается: нафига писал тогда.. хахаха
Я вообще не программист, ничего в этом не понимаю и ни одного кода в жизни не написал, но, первое, что мне на ум пришло: проверить число с координатами n/2 и m/2 (округление не важно, можно в любую сторону). Если оно больше искомого, то это отсекает 1/4 массива. Дальше снова ищем некую середину и повторяем процесс. Если же оно меньше искомого, то это отсекает 3/4 массива. В любом случае, это на каждой итерации сильно сокращает объём поиска. Не судите строго. Возможно, вообще бред написал ) Не специалист )
Я бы прошëлся по диагонали с левого верхнего угла вниз (1, 5, 9, 17), остановился бы, как только наткнулся на число, больше К, и в этой строке начал отстëгивать числа влево, до тех пор, пока не добрался бы до числа К (вернул бы тру), или пока не добрался бы до числа меньше К или до начала строки. Тогда бы я взял предыдущую строку и от числа по диагонали стал бы отстëгивать направо числа. Попалось бы число К - вернул тру, добрался бы до числа больше К или до конца строки - вернул фолс. Как-то так 🙃
да, так же подумал как в решении, только сравнивать не "то что меньше", а "то что больше" (возможно менее эффективное решение). Т.е. если K больше чем a(n-1,m) то двигаться вниз. И еще я бы ввел проверку на "крайние" условия типа к !=0 и a(n,m) >=k
Для любого числа можно уменьшить фактическое время вычисления. Если определить с верхнего правого угла или с нижнего левого угла начать выполнение представленного алгоритма. Путем сравнения в два шага. Да, добавляется несколько действий. Но статистически это ухудшит время только для чисел, находящихся по центру. А фактически это увеличит скорость для всех остальных случаев, когда искомое находится дальше центра при отсчете с верхнего угла (начала пути алгоритма).
тогда можно и вовсе чекать ячейки рандомно. Да не самый оптимальный вариант, будет стремится к середине, но зато подойдет для любой не отсортированной матрицы)
я догадался где-то за минуту, но зачем начинать с последнего столбца я не понимаю, по мне так никакой разницы нет, число может оказаться как маленьким так и большим. Правда можно просто в начале проверить минимальное и максимальное значение чтобы упростить поиск false.
С последнего столбца начинать удобнее, тк можно двигаться всего по-одному принципу: если необходимое число больше текущего - мы всегда идем вниз, если меньше - всегда влево. Если вы начнете с первого столбца - вам придется либо менять формулу в процессе, либо усложнять ее.
Нет никакой разницы по диагонале ты идешь или нет. Первое решение что пришло на ум проще твоего. Сначала цикл по первому столбцу - ищем номер строки. Сравниваем цифры в первом столбце с 14. 1
Похоже что не будет лучше Ваш алгоритм. К примеру если число боллее 18, то ещё по одному столбцу придётся пройтись. К примеру надо найти 25 алгоритм автора на несколько сравнений быстрее. Ваш алгоритм хорош, если число меньше нижнего в 1(то есть нулевом) столбце. Но если нет, тогда очень высока вероятность прохождения ещё одного столбца, а это уже О(n+2*m) или что-то вроде этого.
Возможно и так. Интересно, как оцениваются задачи по понятности решения для того, кому потом придется это сапортить, и пригодности для рефакторинга. Как по мне, два миницикла более читаемы, более разбиваемы на отдельные методы чем один большой цикл, в котором всё. Если читаемость на первом месте то допустимо ли немного пожертвовать производительностью? Есть такое понятие как самодокументированный код. То есть, не содержащий отдельного джавадока или доп комментов, но разбит на маленькие методы, которые в названии содержат суть кода.
@@VovaAleksandrovich Не являюсь програмистом (только полтора месяца назад начал изучать джаву самостоятельно), но согласен с Вами - читабельность хорошо и думаю можно немного пожертвовать производительностью во многих случаях.
Есть решение даже за лог(нм) = лог(н) + лог(м). А именно можно бинарить в бинипоиске, проще говоря бинарить площадь прямоугольника в котором предпологаемое число к, для этого берем центральный столбец и бинарим в нем к, нашли первое i не меньшее к, тогда если поделить условно прямоугольник i-ой строкой и центральным столбцом на 4 четверти (типа декартовых) то к точно нету в 2 и 4 четвертях, тогда рекурсивро запускаемя из полученный прямоугольников в 1 и 3 четвертях и решаем задачу за лог(нм)
Идея хорошая, но оценка времени работы неправильная. Можно придумать такой тест, что ваш алгоритм всегда будет рекурсивно запускаться из двух примерно равных прямоугольников, тогда время работы на этом тесте будет выражаться рекурретной T(nm) = 2 * T(nm/4) + C = O((nm)^log_4(2)) = O(sqrt(nm)), что сопоставимо O(n + m) при n ~= m. (причём я пренебрёг логарифмом от кол-ва строк в рекурренте - просто константу подставил)
У меня почти такая же идея пришла в голову (то есть суть сводится к разбиению на 4 четверти и уменьшению площади в два раза). Но можно алгоритм сделать чуть лучше по мат. ожиданию сложности - резать не центральным столбцом, а делать дихотомию по диагонали (из левого верхнего угла). Сложность худшего случая останется такой же (как верно уточнил solacerxt) - O(n+m). Но ожидаемое время работы такого подхода будет O(log(n)*log(m)). Разрез же центральным столбцом ухудшает ожидаемое время работы и приближает его к О(n+m).
Да, это у меня в Гугле спросили на собеседовании. Не решил. На мой персональный взгляд, это задачка на сообразительность, а не на структуры и алгоритмы. Мое персональное мнение, что задачи такого типа не подходят для интервью. Объясню. Задачи на сообразительность отбраковывают слишком много хороших кандидатов которые честно готовились и знают достаточно много, но не готовились решать задачи вот конкретно такого типа. Даже можно сообразить про негласную диагональ, но это не является функцией глубины понимания предмета, а чисто функцией натаскивание на решение таких задач. Успешно работаю у конкурента Гугла много лет, сам проводил множество интервью, знаю, о чем говорю.
Солидарен. Если каждый день такие задачки решать, то мышление подстраивается под это. И в итоге, даже конченный дегенерат сможет такое решать уже просто на автоматизме. Так что, берем в гугл?) Раньше увлекался головоломками поэтому знакомо
Придумал такое же решение, но начинал с левой стороны, а когда прослушал решение, понял что я сделал лишнее действие - переводил каретку в правую сторону, а потом решал так же как и нужно в лево и в низ.
А почему не сделать бинпоиск по главной диагонали, за log(n) найти пару чисел на главной диагонали (x, y) и (x+1, y+1), между которыми расположено наше и дальше наше искомое число может находиться либо в строке x+1, либо в столбце y+1, и там и там делаем также бинпоиск. Получается 2 log(n) + log(m), то есть O(log(n) + log(m))
Потому что искомое число может находится справа от столбца y+1 вплоть до последнего, а так же ниже строки x+1 вплоть до самой нижней строки. А значит проверка только строки x+1 и столбца y+1 гарантированно число не найдёт.
Не будет такой сложности. В худшем случае так и останется O(n+m). Можно уменьшить ожидаемую сложность, но опять таки не до O(log(n+m)), а до O(log(n)*log(m)).
Видео на паузе. Вот кая я бы попытался решить эту задачу. По условию числа идут по возрастанию. Поиск числа начал с определьния на какой строке и столбце массива находится предполагаемое число, по крайним значениям в строках и столбцах. Далее задачу можно решить или простым перебором всех значений в найденых строке и столбце, или берем значение массива, которое находится посередине найденных строк, столбцов и смотрим. Смотрим где находится наше число, до середины и после. Повторяем эту операцию п-количество раз пока найдем или не найдем нужное нам число.
Решение ещё не слушал, но поиск в ширину со списком очереди напрашивается сам собой. Если первый элемент меньше 14, то добавляем в очередь следующие ячейки по столбцу и строке.
Решение пришедшее на ум в первые 30сек. Ищем по диагонали с top left to bottom right. Находим искомое число на диагонали. Если его нет и следующее больше: проверяем только 2 числа: справа от меньшего и слева от большего. И все. Может где-то и протупил, но по идее должно работать.
Создал Telegram канал, в котором рассказываю о жизни в Лондоне, работе в Google и подготовке к собеседованиям. Подписывайтесь: t.me/saschalukin
После того когда находишь более менее краткий путь к нужному результату всегда так на душе приятно становится. Внутренний перфекционист удовлетворен.
Неприятно только одно, чтобы найти этот краткий путь, пришлось перебрать все пути не краткие 🤣
И всегда найдётся азиат, который сделает это быстрее и лучше)
Только под массовость такое решение не подойдет. А значит придется писать отдельный код под разные матрицы
Самый лучший путь решения - отдать любому индусу на аутсорс))
5:10 ну как так-то хоть бы на словах надо было метод золотого сечения упомянуть да и вообще можно тупо делить пополам.
На собеседовании в амазон:
-Вы умеете не ходить в туалет 12 часов?
-Да
-Вы приняты.
На собеседовании в ЕА Games
- Вы радикальная феминистка?
- Да
- Вы приняты.
Все эти задачки мне почему-то напомнили как один парень у нас в универе сдавал зачёты, подходил к одному спрашивал что спрашивает препод, потом к другому, потом к третьему, в общем так он перебирал абсолютно все варианты что спрашивал препод по конкретной лабе и потом сдавал её.
Но стоило преподу однажды перед ним поставить новую задачу, которую он никогда ни у одного студента не спрашивал, как всё хорошее и закончилось.
Вероятность появления такой пары оригинальных (преподаватель;вопрос) мала, поэтому метод опроса надежен
@@andrewmurruvyov4359 Это я к тому, что нафига вообще рассматривать методы решения задач, ну вот знаете вы как решить эту конкретную задачу в гугл на миллион долларов в год, а дай вам новую как всё хорошее и закончится, и нифига вы её уже не решите, потому что вы как этот парень из универа, вместо того чтобы учиться решать самому, тупо спрашивал у всех и перебирал все возможные варианты, а сам решать так и не научился, надо учится самому решать, а не смотреть на решения других людей и думать что теперь я мега умный и сам смогу решить такую задачу.
Как говорится: всё просто когда знаешь как, а если не знаешь, то и таблица умножения кажется мега сложной задачей.
Экзамен сдаёт не тот кто умеет решать, а кто умеет сдавать, и на работу устраивается не тот кто может работать, а кто может проходить интервью
@@andrewmurruvyov4359 как правило такие говноработники которые не умеют работать, а умеют устраиваться, потом долго не работают. потому что потом уже НАДО РАБОТАТЬ, а не сдавать 🤣🤣🤣
@@andrewmurruvyov4359 а как этому научиться, если ты бездарь?
Офигеть, до твоих видео вообще не решал алгоритмы и оказывается они намного легче чем я думал. Да и это видео просто change my mind
Когда объяснение под рукой то кажется легче, чем есть на самом деле
На самом деле самому решать не так легко
А что забавнее, что эти задачи мало кто решает так изящно сам по себе, фактически все учат только принципы и шаблоны, которых не так много. Это большой труд, но как это помогает определить хорошего программиста - вопрос :)
@@Hello-g5b3p не программисту будет лень
@@Hello-g5b3p, всё зависит от того, для решения каких задач нужен программист. Хороший программист для одних, ужасен для других.
Скажем, задача та же, только у в распоряжении лишь три регистра и только один из них имеет ёмкость достаточную для указания на ячейку в матрице, при этом никто не лимитирует алгоритм по времени.
Практическое применение: микроконтроллер без ОЗУ, все прочие регистры заняты другими данными всей микропрограммы, а её частью является алгоритм, микроконтроллер может 16 MIPS, а управляет дверным замком (то есть, даже если на сравнение уйдёт 30000 выполненных операций для матрицы 6*7, то это всего лишь задержка 0,001875 секунды, что человек в принципе не в состоянии заметить, да и замок открываться в следствии наличия инерции засова всё равно будет открываться дольше). И написать надо всё естественно на ассемблере.
Так что, да, очень актуальен вопрос - как определить хорошего программиста?
как всегда кайф смотреть, хорошо сделано! подача отличная, даже я всё понял, не зная ничего об этом! давай еще и побольше лайв контента!)
Такая чистая, приятная и понятная подача, спасибо!
Блин, это так просто и так гениально... мне стыдно, что я не додумался до такого решения сам
жиза
ты просто всю жизь не курил и не бухал и мухоморы не жевал. А Бог - есть!
@@alexanders8928 Обычно, когда вспоминаешь все мухоморные дела, ты уже сеньор))
Еще проще решение - копируешь цифры в чат gpt и просишь его найти нужное))
Это вообще не гениально. Это очень даже тупо.
проблема взялась из ниоткуда и мужественно решена ... браво
Так суть программирования в том что всегда появляются "проблемы" которые нужно "мужественно" решать)
Удивительно, но почему то сразу пришел к такому решения 😮 Задача крута! Спасибо!
we can do 2 binary searches,
firstly we can go through the rows and find the right row(if the target is greater than the midRow's last element then startRow=midRow+1), and then do a binary search only for that row,
in that case we will have O(logn + logm).
This won't work. Try to find 8 using your algorithm in the example provided in the video.
Однако решить с такой сложностью всё таки можно если заметить, что для произвольного элемента m[i][j]
@@dmitryzhuk220 Не скажу что быстрее чем в видео нельзя решить, я как раз сейчас думаю над этим, но если элемент m[i][j] < k, то можно сказать лишь что наш элемент находится НЕ выше и левее, а иначе НЕ ниже и правее, то есть мы можем отрезать прямоугольную подматрицу в которой элемент не находится, но не выделить онную
@@mrseeker9075 о, действительно, спасибо за уточнение
@@mrseeker9075по идее матрицу можно нарезать на 4 меньшие матрицы (относительно ключевого элемента в центре) а потом рекурсивно повторять алгоритм до размера в 1 элемент и просто проверять этот 1 элемент на равенство. Единственное что есть риск переполнения стека на огромных матрицах
С возвращением, Саша. Так мало качественных разборов нынче!
Сразу подумал что нужно идти по диагонали.
Вот только не объяснил почему с правого верхнего угла пошли. Без разницы с какого угла идти, числом может быть как ближе к наименьшему так и ближе к на большему, соответственно если искомое число например 2 то поиск будет максимально долгим.
Решение этой задачи можно немного оптимизировать так: mid = (max + min) / 2
Если n < mid то идём по диагонали с верхнего левого угла, если n > mid то с правого верхнего угла. Дальше действуем без изменений.
Я в целом решил таким же образом, только начинал с левого верхнего угла и не считаю, что этот метод менее эффективен. Просто в данном случае, у нас 4 столбца с числами меньше 14 и 2 с числами больше 14,но возможна и обратная ситуация
опиши алгоритм
При k=5 выгоднее начинать с левого верхнего угла, а при k=24 выгоднее начинать с правого нижнего угла.
Поэтому начинают с середины, как в обычном бинарном поиске: либо с правого верхнего угла, либо с левого нижнего угла.
@@РоманБондарь-м3е Мне показалось правильными начинать с правого нижнего. Ну то есть если бы мне дали 5 минут подумать, то мой вариант был бы таким. Хоть и не оптимальный.
Левый верхний менее эффективен, нужно откатываться назад на 1 столбец упираясь в большее в следующем. Двигаться будем не по прямой (приближенной к прямой "траектории"), а "зигзагами".
Представьте, что это не просто матрица, а пиксели на дисплее и каждая ваша выборка данных из матрицы закрашивает пиксель, увидите траекторию.
Я тоже не понял разницы начинать именно справа
если постараться можно уменьшить до O(log(n)+log(m)) для этого надо заменить нахождение спомощю шагов на два бинарных поиска
Если постараться...
Как ты поймешь что пора заканчивать делать бин. поиск по текущей оси и пора начинать делать бин. поиск по другой?
@@desmosmech7037 Признак конца поиска по строкам это два соседа
один меньше
другой больше
бери меньший и ищи в этой строке
@@smarthedgehog3185 "бери меньший и ищи в этой строке" Если я правильно понял, то из примера на доске, вы найдете стоблец (11, 12, 16...) Но в нем нет 14)
Мне кажется человек не понял задачу.
Но чтоб получить такую асимптотику надо сделать мёрдж, в один массив, но без пред обработки удачи.
@@roket132 Мы ищем сначало строку а потом в строке нужное поле.
В строке между 10 и 18 есть 14. 14 какраза в строе с 10
Вот честно поставил на паузу на 2:24: я бы использовал что-то типа волнового алгоритма. Начинаем с элемента (0;0) и смотрим всех его соседей (по 8 направлениям, где это возможно), если среди соседей нет числа К, то перемещаемся на позицию максимального числа; в нашем случае (1;1) со значением 5 и так до тех пор пока у текущего элемента не будет соседа со значением 5, ну плюс ещё условие выхода из цикла со значением false, если вдруг текущее значение стало больше К.
Теперь по честному нажимаю play и смотрю дальше 😀
Александр, крутые видео, записывай ещё ) интересно было бы про все этапы собеседования услышать в одном ролике
эх, не удалось решить самому так элегантно, не додумался до возможности начать справа сверху, только левый верх и правый низ рассматривал) отличный разбор!
❤ хоть у тебя и мало разборов, но они очень информативные, может будет хотя бы по 3 задачи в неделю - контент мега полезный, особенно для джунов. В Яндексе дают похожие.
Чувак, я ничего не понял что ты сказал. Но когда ты стал говорить, ты достучался до моего сердца
Пфф, нашел за секунду: вот оно число, на четвёртой строчке, в третьем столбце
Спасибо за задачу. Кажется, что если на каждой строке или столбце, по которым мы передвигались из верхнего правого угла до 14, сделать бинарный поиск, то можно получить что-то около logN + logM
помойму можно матрицу намутить, в который ты больше одного шага по прямой не сможешь сделать
А зачем бинарный поиск? Мы по порядку идём. Он на больших массивах только замедлит.
А если матрица с рандомными числами будет? Придется переделывать
Ага)
Тоже возникла такая мысль. По сути, он для каждой строки ищет число, которое было бы меньше N, чтобы по этому столбцу далее найти число, котоое было бы больше N. И снова по строке, по столбцу и т.д.
отличное объяснение, надо больше таких накидать Александр)
оптимальное решение быстрее. основная логика та же, но начинать надо не с левого верхнего угла, а с "середины"матрицы. правда надо будет немного заморочиться с обработкой вариантов. зато средняя скорость решения примерно в 2 раза выше получится.
Во-первых - 2 раза быстрее не получится, тк мы теряем возможность двигаться по диагонали в одном направлении - тк если число, которое мы ищем, например, больше "серединного" - то оно может быть как правее, так и ниже.
А во-вторых O(n/2+m/2) = O(n+m). Так что усложняя себе жизнь, вы не получаете никаких бонусов.
@@oleksandr2234 да, я тоже об этом подумал, но в целом ожидаю что ускорение до 2 раз реально
До такого решения не додумался бы сам, по крайней мере за 10 минут. Спасибо за пример!
Примерно такое же решение с поиском таргетного числа вокруг текущего в голову пришло,
Только мне пришло в голову стартовой точкой задать не верхний правый угол а середину (по аналогии с бинарным поиском).
В результате при прогоне данной матрицы от 0 до 36, разница в шагах внутри цикла составила 214 (твое решение со стартовой точкой в углу) против 127 со стартовой точкой в центре.
Центр находил абсолютно банально через Math.floor(arr.length / 2) и Math.floor((arr[0].length - 1) / 2);
Вроде как шустрее почти в два раза получается :)
Спасибо за задачу!
Тоже самое подумал, про центр сразу. Да и к тому же можно внести ещё одну оптимизацию, тем более если известен характер чисел (насколько случайные числа были отсортированы и какая случайность использовалась) Можно брать не крайний верхний угол, а относительный порядковый номер диагонали беря во внимание крайние значения таблицы. К примеру видим что таблица начинается с 1 и заканчивается 36. А надо найти число 14, тогда делим искомое число, на разницу начального числа таблицы и конечного. Получаем 0.4. Далее умножаем 0.4 на размерность таблицы и далее округляем числа. И получаем координату оптимального старта поиска, чем линейнее распределение, тем точнее будет координата старта.
@@ТёмикГоловин-й8ц Никто не обещал линейного распределения. А где такие задания на собеседования даются?
@@The14Some1 Понятное дело не обещал. Просто так алгоритм будет работать быстрее на больших размерностях и при разных функциях распределениях и незначительно медленнее на малых размерностях и не линейных функциях распределения
Круто. А главное красиво.Лично мне первое пришедшее в голову решение было:
1) берем среднее по номеру число в средней строке. Если такого нет - ближайшее (к примеру 7 если всего 15. Или 8. Без разницы). Мысленно мы разделили по строке и столбцу на 4 секции. Если К меньше числа, то мы отсекаем все большие числа по строке и столбцу. И повторяем это всё.
В программировании я совершенно не разбираюсь, думала с точки зрения математики скорее.
была детская задачка отгадать число от 1 до 1024 за 10 попыток. тебе говорят больше или меньше задуманного то что ты назвал. лень проверять, но думаю такой способ более эффективен чем предложенный.
Да, этот способ является самым эффективным и называется двоичным поиском.
@@QuarkWasp, двоичный поиск работает с линейными массивами. Такую матрицу к линейному массиву свести очень дорого.
Ловко ты мне в рекомендациях попался, не зря в гугле работаешь)
с левого верхнего угла на каждом шаге выбирать элемент правее и элемент ниже. сравнивать эти 2 соседних элемента и двигаться по пути наименьшего из выбранных пока не пересечемся с искомым или не превысим его значение. подход аналогичен описанному но только более понятен
Найди по этому алгоритму число 7 или 11
не работает. Тебя может увести слишком далеко вправо, или слишком далеко вниз.
Решил так же! Почти ) Понял, что надо идти лесенкой. Сперва в 1-й строке найти число большее к, сдвинуться к предыдущему индексу в строке, увеличить индекс по вертикали. Все, как вы описали. Единственное отличие - я пошел слева направо. Вам хорошо, вы видите все значения в массиве, а программа их не видит. Первое же левое число в строке может быть к! Или другое, достаточно "левое" число. Нет никаких преимуществ у больших чисел справа перед меньшими числами слева - к может стоять ближе как к левому, так и к правому краю.
Неплохо было бы еще двоичный поиск min числа > к в 1-й строке добавить! Потому, как можно почти всю строку пропахать в поисках такого числа, а оно окажется ближе к краю, противоположной началу поиска.
Спасибо за задачу! Понравилась.
Я так же подумал, но понял что делается одно лишнее движение каретки с лева на право. А потом в итоге каретка движется с права на лево и в низ.
Друг, есть более быстрый способ. Первое, проверяем число в ячейке 1,1 и m,n убеждаемся что число К в середине и переборку начинаем с середины в таком случае получаем O((m+n)/2). Можно конечно и не проверять начало с концом тогда, тогда, если брать худший сценарий будет еще быстрее, однако если брать лучший сценарий то можно и без переборки сказать что нет числа в матрице
Что есть середина матрицы 2х10? Мы должны курсор поставить в 1,5? А, может, в 2,6? Но мысль красивая с проверкой 1,1 и m,n. Если искомое число не в матрице (меньше наименьшего элемента или больше наибольшего), то выполним за 1 или 2 операции)
@@Rofelka в предложенной Вами матрице 1,5 1,6 2,5 2,6 равнозначны
@@АлександрКраснов-н5ж Допустим дана матрица 100х200, надо найти число К=14. Вы начали с середины, там число 50. Все что вы теперь знаете, это то, что правую нижнюю часть можно отбросить. Но куда теперь вам дальше двигаться? Число К может быть в любой из трёх оставшихся областей. Причем оно может быть как левее середины, так и правее, как ниже середины, так и выше.
@@SayXaNow точно, мой способ получается О(1.5 (m+n))
@@SayXaNow а если дальше опять повторить ход в середину оставшейся области? то есть по сути всегда делим на 2 и сверяем....и того вместо 7 будет 5 ходов
Ваше решение занимает, на данном примере, 7 шагов. Мое 5-6. Именно с угла, откуда, по Вашим словам, нет смысла начинать. А именно. Смотрим первую цифру. Если =14, то тру. Если больше - фолз. Если меньше - делаем шаг n+1 и m+1. Т.е. по диагонали. Те же условия, за исключением того, что если больше 14, то проверяем 2 числа по краям диагонали. Итого, в конкретном примере, Ваше решение идет по числам 16-15-11-12-16-9-14, выдавая "тру" с седьмой проверки. Мое идет по 1-5-9-17-16-14 (или 1-5-9-17-14) выдавая результат с 5-6 раза. Всего, максимум шагов, для проверки всех чисел матрицы, у Вас может быть 10 (кратчайший прямой путь от верхнего правого до нижнего левого угла). В моем случае - 7. 5 на диагональ - 2 на проверку рядом с диагональю. (в данном примере, после числа 30 проверяется 36 и 27, если они были бы меньше или равны 14). Отсюда вывод - Ваше решение не оптимально. Могу кодом, если так проще воспринимать.
k = 18. Алгоритм за 7 шагов сказал, что такого числа нет. Двигатель шаттла №18 не запустился, ракета упала.
@@SayXaNow примерно так, да. Проглючило. Даже не задумался, что оно не на диагонали может быть) Сам потом понял, но уже не стал ничего удалять)
но моя идея состояла в том чтобы идти исключительно по диагонали допустим слева направо... тобишь arr[0][0] далее arr[1][1] и так далее на перекрестии будет цифра либо отсекающая сектор точно меньше либо точно больше и потом нужно будет только вернуться от этой цифры вверх или вниз
проблема идти по диагонали в том, что ты не знаешь куда поворачивать как только найдешь значение больше искомого, а значит придется запоминать в какой момент ты повернул и в какую сторону, если же идти по вертикали/горизонтали и влево-вправо/вверх-вниз, то ничего запоминать не придется
Видимо мы думаем по-разному.
Двигаемся с 0,0 по главной диагонали пока значение ячейки не станет больше искомого (17)
Далее просто проверяем все значения строки, столбца (17).
Самое быстрое решение, которое я смог найти, вот такое:
Находим центральную строку, бинарным поиском делим её на две части - до и после искомого числа.
Проводим от этой точки мысленную горизонтальную и вертикальную линию, тем самым разделив таблицу на 4 части.
Левый верхний угол выкидываем, там все числа меньше искомого. Правый нижний тоже выкидываем, там все числа больше. А в левом нижнем и в правом верхнем углах запускаем этот алгоритм рекурсивно. Получаем логарифмическое время посика. P.S. видос ещё не смотрел.
мне тоже кажется делить на квадраты интересная идея, первое что пришло на ум, до просмотра решения)
Отличное решение, масштабируемое! Тоже думаю надо отталкиваться от центра в этой задаче, путь из одного конца матрицы в другой может быть слишком долгим
квадраты получаются только не квадратные в данной матрице
Как я и думал, можно за log(m+n)
Ты можешь исключить только один квадрат за шаг
хочу быть таким же умным парнем как ты✊
То, что сразу полезло в голову:
1) Проходимся по каждому элементу первой строки и ищём первое число, которое будет больше k
2) Делаем то же, но для первого столбца
3) Ограничиваем область поиска k найденными ранее элементами массива
4) Используем любой поиск.
В худшем случае ограничение у нас займёт O(n+m), а поиск - O(n1 * m1), где n1 и m1 - элементы-ограничители (при прохождении по каждому элементу).
Ух-ты, тоже это в голову пришло
Можно еще ограничивать область если найти число которое меньше k (не рассматривать левую верхнюю область). И тогда такое решение может быть даже быстрее чем то которое рассказали.
@@realvaniog, объясните пошагово. Звучит как бред.
В худшем случае (k>18), а это почти половина возможных k, размер матрицы не уменьшается. Но ваше решение натолкнуло меня на другое. Нужно, чтобы опытный алгоритмист проверил, может я тоже не прав.
Решение:
1) в первой строке доходим до последнего =к. Зачеркиваем для себя все, что ниже.
3) в уже ограниченой матрице идем по первому столбцу до последнего =к. Зачеркиваем для себя, все что левее.
Проходки логично делать бинарным поиском. Если я все правильно понимаю по крайней мере в этой таблице за эти 4 этапа находим наше число. Если таблица больше надо пример, чтобы понять что дальше делать, но так мы гарантированно сильно уменьшаем зону поиска.
Получается 2log(m) + 2log(n)
@@OstapP Если нашли число меньшее k, то нам не подходят все числа которые (одновременно) левее и выше этого найденного числа (там все числа меньше k). Аналогично с числом большим k. Т.о любое число неравное k ограничивает нашу область поиска.
Отличный формат!
Отлично, первая же идея была довольно близка. Осталось самую малость, научиться кодить 😅
Жара! Нравится мне программирование.
Жаль только, что на собесах не обеспокоены качеством кода, а только задачками. Каждый раз, когда приходится обновлять сервисы гугла: firebase, admob, playgames - молишься, как бы хуже не стало. Ошибки без исправлений годами висят. Примерчик: подключаешь любой самый ссаный рекламный провайдер и ANR в норме, подключаешь admob и ANR в космос летит.
Странно, меня вот в одном из собеседований на трейни отшили именно по причине, что я не пользовался модулями и недостаточно явно поделил логику и вывод. А в другом отшили за то, что я это сделал, а они выбрали кандидатов, предпочёвших более простые решения.
Кажется, что задачу можно решить за О(log(m+n)). Надо в упорядоченной линии, которая похожа на диагональ матрицы( длина m+n) найти наибольшее число меньше искомого( это называется правосторонний поиск ). Следующее число будет больше искомого. Вместе они образуют матрицу 2х2. Осталось проверить оставшиеся два элемента матрицы на совпадение с искомым.
Можно так же с левого нижнего угла начинать. Там работают теже правила, только в другом направлении
С левого верхнего угла тоже можно.
@@kaxan1407 Вообще-то нет)) У тебя с обоих сторон числа больше в таком случае. Ты просто не можешь определить, куда идти
@@niqr7800 да, я понел что в общем случае это не сработает минут через 5 после написания коммента
Хороший результат, линейный алгоритм оптимизированный для двумерного случая. Для еще более быстрого поиска можно бинарный поиском найти строку и далее найти столбец также бинарным поиском. Сложность будет еще меньше.
Ваш алгоритм даст быстрый неправильный овет для 11, 12, 15, 16, ....
@@OstapP я написал не то что подумал, бинарным поиском искать и столбец и строку. Ответ будет правильным так как и там и там отсортированные множества
@@yoptaman9000 , можно этапно? Я не понял ваш алгоритм.
В принципе всё правильно. Но исходя из того-же бинарного принципа начинать надо не с краёв а с середины. То есть с числа 16. Ну и идти придётся не в одну сторону, а в зависимости от сравнения.
В данном конкретном случае дойдём до 14 за 2 хода 🙂
Ну да, первое желание всё-таки получить $O(\ln n + \ln m)$, а не $O(n+m)$...
левый нижний и правый верхний углы для линейного алгоритма - это две единственные ключевые точки из которых за одно сравнение существует только один единственный путь движения. для любой другой стартовой точки матрицы таких пути уже два. но нормальные люди в упорядоченных последовательностях ищут бинарным поиском по строкам, начиная с граней
@@SayXaNowтоже подумал о бинарном поиске
@@SayXaNow
Я вот как думаю:
- В принципе даже условие задачи не совсем строгое - что такое самый быстрый (или оптимальный) алгоритм поиска?
- В общем случае я вижу как минимум 2 интерпретации.
- 1 - Минимальное количество шагов в среднем.
- 2 - Минимизировать количество шагов для самого плохого случая.
Очевидно, что алгиритмы получатся разные.
Для второго алгоритма, особенно для большого количества рядов (например 1 000 000 000) не оптимально двигаться последовательно по лесенке.
Надо целый массив разбивать на кучки (на 2, а лучше на 3), проверять граничные условия прыгая из одной в другую и убирать целые кучки (суб массивы).
Когда осталась кучка небольшого размера (надо считать какого), тогда уже можно идти по лесенке от верхнего правого угла...
Ну может я и не прав???
@@Proezdom-zx2tl Ну задача с подвохом. я всегда топил и топлю за бинарный алгоритм. В матрице случайных упорядоченных значений размером 2500х10000 он показывает скорость нахождения любого элемента в среднем за 67 шагов. Казалось бы - фантастика, ну что за лохи вообще топят за этот линейный аутизм, ведь налицо логарифмическая скорость.
Но надо учесть один нюанс. могут попадаться квадратные блоки данных, в которых числа расположены особым образом и полностью удовлетворяют условию задачи (правее всегда числа больше, снизу от любого числа тоже всегда больше), но для которых не существует в принципе алгоритма быстрее, чем линейный ступеньками.
И если вдруг в моей матрице мне попался именно такой блок размером 2500х2500 то максимально неудачный расклад для бинарного поиска составит 50000 шагов и примерно 15000 в среднем для любого числа такого блока. Не трудно посчитать что неторопливый линейный тут покажет лучший результат. И т.к. никаким способом нельзя быстро проверить попался нам такой блок или нет, я бы не рискнул использовать быструю бинарку для слишком больших квадратных матриц. Сначала бы убедился что большая сторона M превосходит меньшую N хотя бы в 5 раз. А если ярко выраженная прямоугольная длинная типа 1000х17000 - тут даже обсуждать нечего - только бинарный поиск.
Страшилка конечно это все, да и вероятность мала нарваться на такое, поэтому юзаю бинарки и не заморачиваюсь. Но как минимум надо помнить теперь об этом. Такие вот любопытные подробности всплыли, когда занимался тестами.
а можно ведь и за 2*log(N). В начале бинарный поиск по колонке, проверяем верхнюю и нижнюю колонку. Если два последних числа в верхней и нижней колонке больше искомого идем внизу, если оба меньше вверх. Если в верхней колонке число меньше искомого, а в нижней нет - мы нашли нужную колонку за O(n)
А дальше уже стандартный бинарный поиск по столбцу
не знаю почему, но думаю это решение можно назвать одним из оптимальных. Как вариант можно использовать информацию, что за числа находятся на вершинах это матрицы и основываясь на этом принимать решение откуда начинать двигаться
Пойму тут O(n) получается, т.е. максимальный путь 2n.. меньше не придумаешь
@@denisgluk431 В этом алгоритме.
Если начинать не с правого верхнего, а n/2 в первой строке и также потом, при спуске.
Пример, n=1000, m=2
а вообще можно совместить и сделать тройное решение тобишь находить быстро точку входа допустим цифру 17 потом от нее идти влево вниз и одновременно вверх вправо
Кажется, что ходить до границы матрицы из верхнего правого угла может быть расточительно. При какой-нибудь матрице 1e12 x 1e12 (абстрактная большая цифра). Может стоить добавить в код условие про то, что если k < верхнего левого угла || k > нижнего правого угла, то искать нет смысла (false).
Ну как раз на этом этапе можно использовать бинарный поиск
В этой матрице выполняется условие, что все элементы левее и выше меньше или равно текущего элемента, а все элементы правее и ниже - больше текущего элемента.
Об элементах левее и ниже и правее и выше ничего однозначно сказать нельзя. Среди них могут встречаться меньшие, равные или большие. Поэтому матрицу надо проходить до конца.
@@dmytrozazulin1858 , по-моему вы либо не так интерпретируете мое сообщение, или не так интерпретируете условие.
Простой вопрос:
Если в правом нижнем углу матрицы значение, равное 500, может ли в матрице быть значение, например, 501?
Если да, составьте пример такой матрицы, я посмотрю, как вы это сделаете, не нарушая условий
@@core2mind Ясно, я думал вы хотите внести коррективы в сам процесс поиска. А это просто проверка вырожденного случая.
@@dmytrozazulin1858 , ну это по сути внесение изменений в алгоритм поиска, но не в алгоритм скана матрицы самой. Если у нас матрица триллион x триллион, есть ли смысл долго по ней ходить, если за константное время можно сразу сделать вывод, что ходить по ней нет смысла. Я это хотел донести, если что.
В алгоритме, представленном в видео, уже есть предварительные проверки перед сканированием матрицы, мой поинт был лишь в том, что возможно стоит расширить эти проверки.
можно еще бинарным поиском попрбовать. Делим на 4 квадранта, смотрим в каждом из них левое верхнее и правое нижнее, и сравниваем с искомым. Например, если первоначальным разбиением взять за центр 16, то правый нижний квадрант можно отсечь и левый верхний квадрант можно отсечь. Далее рекурсивно ищем в правом верхнем и в левом нижнем.
Тоже об этом подумал. Тогда сложно сложность О(log_2(m+n)). Еще быстрее выходит.
@@VishnevskyMike в две подматрицы залядывать часто придётся.. а это всё равно на начальную оценку похоже.. O(n)
@@denisgluk431 нет. Даже если в 3 подматрицы придется заглядывать, оценка будет логарифмической, так как на каждой итерации пространство поиска сужается на множитель, а не на константу. А в более чем 3 подматрицы смотреть гарантированно будет не нужно.
А если взять 1 число - середину матрицы, и смотреть если число меньше 14 смотреть правое и снизу; дальше выбирать то, которое больше 14 и меньше второго? И двигаться таким полукрестом. Как скорость оценить?
А идея хорошая, если это правильный алгоритм, сложность будет log(n+m). По сути бинпоиск по диагонали
@@chalex2k Я проверил, правильный и работает
Я конечно не эксперт, но я сразу нашел число 14. Было трудно, просто включил монитор на котором смотрел это увлекательное видео.
Изменено: не работает(
Мне кажется есть не менее эффективный способ, хотя хз насколько он будет лучше в коде.
1) делим количество строк на 2 (округляя) и начинаем с этой цифры. (В данном случае 3)
2) если число меньше то идем вверх, больше вниз. (В данном случае вниз, доходя до 10)
3) теперь также делим уже столбцы (и округляем, в данном случае это не нужно, но при изменении условий пригодилось бы), то есть мы на числе 14.
4) Если число меньше то идем в лево, если больше в право. Но в данной ситуации это не пригодилось.
В чем же преимущество этого метода?
Если считать именно колличество ходов их будет максимум 7. (Если ищем число 36)
В случае описанном в видео 10. (Если ищем число 18)
Найди число 11 по даному алгоритму
@@desmosmech7037 Это просто крайний случай для бинарного поиска по строкам. Ничего не меняет.
Бинарный поиск это метод сходящихся интервалов. Ты просто ускоряешь их сходимость деля на два длину.
В Численных методах этот метод ещё называли поиском льва в пустыне :)
Грубо говоря там можно и площади делить отрезком.
Т.е. сначала делить матрицу по столбцам потом по строкам в зависимости от того какая часть длиннее.
@@desmosmech7037 верно, спасибо что сказал.
Можно ещё быстрее, если начинать проверку с любой цифры в центре матрицы. Тогда ты найдёшь ответ в среднем В ДВА РАЗА БЫСТРЕЕ, чем ты показал. Это вааще очевидно.
Первая (и последняя идея)
1)Проверить первый столбец и первую строку на наличие цифр больше 14 и отсечь их. В нашем случае матрица станет 4 на 4.
2) проверить в обратном порядке последний столбец и строку новой матрицы (4 на 4) и отсечь все, что меньше 14. (Осталось 2 на 2)
3) оставшуюся маленькую матрицу просто перебрать
А потом я досмотрел видео и в очередной раз понял, что я тупой
Вау! Красивое решение!
Сразу придумал бинпоиск. И еще бинпоиском по первому и последнему столбцу можно убрать часть строк, в которых точно нет искомого числа. Но это асимптотику не улучшит.
а если число столбцов очень большее? а К находится ближе в первой половине или еще ближе к левой части? ( не будет ли разумно сравнить число К с количеством столбцов так как данные в матрице натуральные числа и начать с самого максимального в котором столбце она может быть?)
Ну, прописать 4 алгоритма для старта с каждого угла. И выбирать угол в зависимости от этого числа. Но это лишний гемор)
ТЕм более что условие задачи поставило конкретное число, а не рандомное
Класс, я бы никогда так не догадался сделать, хотя очень правильный шаг
Сильно сложный алгоритм поиска, и не факт, что он применим для разных вариантов этой матрицы, мне кажется, что по этой причине тут и повторяются числа.
А мне показалось, что надо начинать с середины матрицы по типу двоичного поиска: 16 > 14, поэтому примерно четверть матрицы вправо и вниз от 16-ти не подходит. И т.д....
Решил меньше чем за минуту, сначала доперев что анализ нужно диагональный проводить и потом уже, что начинать лучше справа налево)
Спасибо. С нетерпением жду следующего разбора.
Блин, а я думал мы умные ) когда 20 лет назад в олимпиаде по матеше участвовал)) Спасибо за видос
Классное решение! Побольше таких видео :)
Аналогично можно начинать с левого нижнего угла, только движемся наверх и вправо
Задача понятна.
Возникает вопрос, а почему идём с правого верхнего угла? Чисто логически можно идти с любого угла. Принцип одинаковый.
С другой стороны если вопрос стоит в скорости то можно попробовать идти с центра. Это если требуется среднюю скорость поиска уменьшить.
Если идти допустим с левого верхнего.
Видим 1, а надо найти 14.
Куда идти? Вправо или вниз?
Принципы разные. Для получения удобной формулы нам нужно идти либо с левого-нижнего, либо с правого-верхнего угла - чтобы иметь однозначное решение если текущее число больше или меньше необходимого.
Как я (не программист) решал примерно такую задачу, не зная наверняка широко известных в узких кругах методов решения подобных задач.
Думаю, что такой метод имеет название, но я назвал его для себя методом сжимающихся границ. Исходно, считаем, что искомое находится между 1-й (нижняя граница) и последней (верхняя граница) строкой. проверяем на средней (понятно, что округляем, промежуток нечётный). После проверки средняя строка становится или новый нижней границей или новой верхней и интервал уменьшается вдвое. И так, пока верхняя не станет равной нижней. После этого аналогичный поиск в этой строке, но уже по столбцам.
Единственное, мне нужен был поиск в массиве из сотен или тысяч строк и столбцов и я делил интервал не пополам, а на 10 частей и, хотя сравнений было больше, сужал интервал в 10 раз. Думаю, что программисты знают более стандартные и быстрый способы, но мой работал, хотя я писал его на VisualBasic (самоучка). Основной проблемой было, что значения в матрице были дробные и нужно было найти значение "примерно" равное. Пришлось придумывать "примерное" сравнение (с заданной точностью), т.к просто округление могло происходить в разные стороны и последняя цифра отличалась. Но это уже другая история)))))
Можно сделать функцию, которая ищет в упорядоченном массиве заданное число, если не находит, то возвращает следующее по убыванию и его индекс.
Тогда алгоритм выглядел бы так:
делаем поиск в первой строчке [1..16] находим 11 и его индекс 3
делаем поиск в первом столбце [1..18] находим 10 и индекс 3
останется сделать поиск заданного числа в подстолбце (0, 3)-(3, 3) это числа [11, 12, 16, 17] и в подстрочке (3, 0)-(3, 3), где значения [10, 13, 14, 17]
сложность не умею точно считать, но вроде должно быть в среднем 1.5*O(log n) + 1.5*O(log m), о том что можно идти змейкой как-то не догадался)
Как увидел, сразу начал по диагонали, но не с того угла. Немного недодумал)) Тем не менее, внутренний "я" доволен собой xD
все круто , он видео почаще бы )
я придумал решение только за m * log n. Ищу в каждой строке нужное число методом бинарного поиска. В общем-то самое элементарное решение если нужна временная сложность меньше, чем O(n * m)
function isK(arr, num) {
for (let i = 0; i < arr.length; i++) {
let left = 0;
let right = arr[i].length - 1;
let center;
while (left num) {
right = center - 1;
} else {
left = center + 1;
}
}
}
return false;
}
Бинарным поиском можно, только их не 1, а 4 нужно написать (за 10 минут можно не успеть).
Пусть сначала область поиска - весь массив.
1. Находим (бин. поиск) последний элемент в первой строке, не превосходящий искомого. Выкидываем область правее данного элемента (там все элементы больше искомого).
2. Находим (бин. поиск) последний элемент в первом столбце, не превосходящий искомого. Выкидываем область ниже данного элемента (там все элементы больше искомого).
3. Находим (опять бин. поиск) первый элемент в последней строке, который больше или равен искомому. Выкидываем область левее данного элемента (там все меньше).
4. Находим (и опять бин. поиск) первый элемент в последнем столбце, который больше или равен искомому. Выкидываем область выше данного элемента (и там все меньше).
Повторяем для полученной меньшей области, пока она не схлопнется до 0 или 1 элемента.
поставив на паузу мне в голову пришло такое решение - идем сначала по первому столбцу и находим строку первый элемент которой БОЛЬШЕ искомого числа , найдя ее мы получаем строку в которой ищем (это предыдущая строка). Далее идем по первой строке и ищем столбец, первый элемент которого БОЛЬШЕ искомого значения, так мы получаем предельный номер столбца (он будет равен найденному минус один), до которого делать поиск в строке найденной на первом шаге. Далее идем по строке определенной на шаге один до столбца найденного на шаге 2 и ищем нужное значение
тут можно еще ускорить алгоритм, если выбор первой точки сделать на основе бинарного поиска, а не просто от правого верхнего значения
Если на то пошло, то оптимальней сначала найти угол с наиболее близким числом и плясать от него. Код увеличится, зато выпоняться будет быстрее всего для любого числа.
бред
Спасибо за видео
Всё очень доступно
Правый верхний угол можно найти дихотомией, что даст еще меньшую оценку, О(logn + m). Далее идти по "диогоналям" можно не поэлементно а также дихотомией, что в общем случае даст O(log n + log m). Такое конечно за 15 минут не написать, но устно я бы обязательно упомянул про более оптимальные пути поиска.
А зачем нужно первое отсечение? Есть инсайдерская информация, что мы так большую часть матрицы выкинем? Дихотомия по диагоналям мне то же пришла в голову, но сложность такого алгоритма останется прежней - O(n+m). Однако ожидаемая сложность такого подхода будет меньше, но не O(log(n)+log(m)), а O(log(n)*log(m)).
@@АнтонДанильченко-е6н, первым отсечением мы сразу уменьшим прямоугольник с m * n до (m-k) * n. В примере на видео - верхний правый элемент с которого можно начинать это 11 (первый элемент меньше 14). Но да, точно, согласен, в случае дихатомаии , оценка будет O(log(m) * log(n)).
Совершено все верно. Использование дихотомии есть самый эффективный метод. Сам решил дихотомией через диагонали, не так сложно как кажется на первый взгляд, ибо алгоритм дихотомии всем известен наизусть.
Диагональная дихотомия - эффективность log(n)^2, где n - наименьшая сторона. Но алгоритм требует рекурсии, т.к. матрица разбивается на каждом шаге на две валидных области, в которых снова применяем алгоритм.
Чередующаяся дихотомия по строкам и столбцам - эффективность log(n)*log(m). Код чуть длиннее, но пишется по факту быстрее и понимается лучше. Не требует рекурсии - что огромнейший плюс.
Окончательный вариант из видео - это фиаско. Применять последовательный поиск в упорядоченной последовательности - это провал собеседования.
@@kostyajan Если по диагоналям отсекать оказывается эффективней, то зачем нужен первый шаг, который может отрезать неопределённое кол-во столбцов (в том числе и 0)?
1. вариант смотрим строку начальное и конечное значение так понимаем есть ли в этой строке искомое число, далее когда поняли какая строка тем же бинарным поиском воспользуемся что бы найти число.
2. Взять самое левое число, самое правое, и так же самое нижнее левое, самое нижнее правое. На основе этого прикинуть в каком примерно месте распологается искомое число.
На основе этого нужен хитрый рандомизатор который из получившегося множества будет выдавать индекс, и там уже сомтреть подходит ли этот индекс. Ну либо в получившемся регионе использовать вариант 1
Написал на Java. Принцип работы - идем по столбцам, перебираем числа в строках каждого столбца. Когда доходим до числа, которое больше K, - переходим на следующий столбец. Если за это время мы находим число, равное K, то возвращаем истину. Если за все итерации не находим число, равное K, то возвращаем ложь.
Сам код:
public class Main {
public static boolean check(int[][] arr, int k) {
int column = 0, m = arr[0].length;
while(column < m) {
for(int[] ints : arr) {
if(ints[column] > k) break;
if(ints[column] == k) return true;
}
column += 1;
}
return false;
}
public static void main(String[] args) {
int k = 14;
int[][] arr = {
{1, 4, 7, 11, 15, 16},
{2, 5, 8, 12, 19, 22},
{3, 6, 9, 16, 22, 24},
{10, 13, 14, 17, 24, 27},
{18, 21, 23, 26, 30, 36}
};
if(check(arr, k)) System.out.println("The given matrix contains the number " + k + ".");
else System.out.println("The given matrix doesn't contain the number " + k + ".");
}
}
Лять... То чувство, когда начал расписывать решение в комментариях, написал, смотришь видос - а тут то же самое решение, и если оставить коммент, то ты будешь выглядеть дурачком каким-то, который зачем-то переписал из видоса, а если удалить, то спрашивается: нафига писал тогда.. хахаха
Можно ещё сократить действий, идя бинарным поиском по верхнему столбцу, а не перебором - в общем случае это уменьшит кол-во шагов
В худшем случае нет. В худшем следующий левый/нижний будет подходящим, а это уже выйдет в O(mlogm + nlogn)
@@ДимаРубин-т6с omnomnomnomnom
Верхний столбец... Интересно, надо записать.
2:39
def searchMatrix(matrix,k):
return any([k in row for row in matrix])
Решение в строку
Я вообще не программист, ничего в этом не понимаю и ни одного кода в жизни не написал, но, первое, что мне на ум пришло: проверить число с координатами n/2 и m/2 (округление не важно, можно в любую сторону). Если оно больше искомого, то это отсекает 1/4 массива. Дальше снова ищем некую середину и повторяем процесс. Если же оно меньше искомого, то это отсекает 3/4 массива.
В любом случае, это на каждой итерации сильно сокращает объём поиска.
Не судите строго. Возможно, вообще бред написал ) Не специалист )
нет. ты все верно написал. просто тут маленькая матрица очень. а вот если там миллион строк на миллион столбцов то ой.
Я бы прошëлся по диагонали с левого верхнего угла вниз (1, 5, 9, 17), остановился бы, как только наткнулся на число, больше К, и в этой строке начал отстëгивать числа влево, до тех пор, пока не добрался бы до числа К (вернул бы тру), или пока не добрался бы до числа меньше К или до начала строки. Тогда бы я взял предыдущую строку и от числа по диагонали стал бы отстëгивать направо числа. Попалось бы число К - вернул тру, добрался бы до числа больше К или до конца строки - вернул фолс. Как-то так 🙃
да, так же подумал как в решении, только сравнивать не "то что меньше", а "то что больше" (возможно менее эффективное решение). Т.е. если K больше чем a(n-1,m) то двигаться вниз. И еще я бы ввел проверку на "крайние" условия типа к !=0 и a(n,m) >=k
Для любого числа можно уменьшить фактическое время вычисления. Если определить с верхнего правого угла или с нижнего левого угла начать выполнение представленного алгоритма. Путем сравнения в два шага. Да, добавляется несколько действий. Но статистически это ухудшит время только для чисел, находящихся по центру. А фактически это увеличит скорость для всех остальных случаев, когда искомое находится дальше центра при отсчете с верхнего угла (начала пути алгоритма).
тогда можно и вовсе чекать ячейки рандомно. Да не самый оптимальный вариант, будет стремится к середине, но зато подойдет для любой не отсортированной матрицы)
@@leofender5753 это алгоритм поиска кратчайшего пути. Более оптимизированный чем в видео.
@@leonidalexeev4098 да, но при рандоме есть шанс найти нужное число вообще за 1 ход)))
@@leofender5753 так я предложил вариант не по рандому, а по алгоритму. За 10000 проходов матрицы размером больше 5 будет более быстрое выполнение.
я догадался где-то за минуту, но зачем начинать с последнего столбца я не понимаю, по мне так никакой разницы нет, число может оказаться как маленьким так и большим. Правда можно просто в начале проверить минимальное и максимальное значение чтобы упростить поиск false.
С последнего столбца начинать удобнее, тк можно двигаться всего по-одному принципу: если необходимое число больше текущего - мы всегда идем вниз, если меньше - всегда влево.
Если вы начнете с первого столбца - вам придется либо менять формулу в процессе, либо усложнять ее.
Нет никакой разницы по диагонале ты идешь или нет. Первое решение что пришло на ум проще твоего. Сначала цикл по первому столбцу - ищем номер строки. Сравниваем цифры в первом столбце с 14. 1
Похоже что не будет лучше Ваш алгоритм. К примеру если число боллее 18, то ещё по одному столбцу придётся пройтись. К примеру надо найти 25 алгоритм автора на несколько сравнений быстрее. Ваш алгоритм хорош, если число меньше нижнего в 1(то есть нулевом) столбце. Но если нет, тогда очень высока вероятность прохождения ещё одного столбца, а это уже О(n+2*m) или что-то вроде этого.
Возможно и так. Интересно, как оцениваются задачи по понятности решения для того, кому потом придется это сапортить, и пригодности для рефакторинга. Как по мне, два миницикла более читаемы, более разбиваемы на отдельные методы чем один большой цикл, в котором всё. Если читаемость на первом месте то допустимо ли немного пожертвовать производительностью? Есть такое понятие как самодокументированный код. То есть, не содержащий отдельного джавадока или доп комментов, но разбит на маленькие методы, которые в названии содержат суть кода.
@@VovaAleksandrovich Не являюсь програмистом (только полтора месяца назад начал изучать джаву самостоятельно), но согласен с Вами - читабельность хорошо и думаю можно немного пожертвовать производительностью во многих случаях.
Красиво! Спасибо за разбор, все четко и по делу.
По первой строке можно добавить двоичный поиск, сильно поможет на больших размерах.
Кстати похоже что на больших матрицах можно выполнять двоичный ограниченный поиск всегда...
Есть решение даже за лог(нм) = лог(н) + лог(м).
А именно можно бинарить в бинипоиске, проще говоря бинарить площадь прямоугольника в котором предпологаемое число к, для этого берем центральный столбец и бинарим в нем к, нашли первое i не меньшее к, тогда если поделить условно прямоугольник i-ой строкой и центральным столбцом на 4 четверти (типа декартовых) то к точно нету в 2 и 4 четвертях, тогда рекурсивро запускаемя из полученный прямоугольников в 1 и 3 четвертях и решаем задачу за лог(нм)
Я так и написал. Останется аккуратно обработать случай, когда один размер станет 1.
Идея хорошая, но оценка времени работы неправильная. Можно придумать такой тест, что ваш алгоритм всегда будет рекурсивно запускаться из двух примерно равных прямоугольников, тогда время работы на этом тесте будет выражаться рекурретной T(nm) = 2 * T(nm/4) + C = O((nm)^log_4(2)) = O(sqrt(nm)), что сопоставимо O(n + m) при n ~= m. (причём я пренебрёг логарифмом от кол-ва строк в рекурренте - просто константу подставил)
Да, согласен конечно, протупил, очевидно, что лог(нм / 4) * 2 > лог(нм)
У меня почти такая же идея пришла в голову (то есть суть сводится к разбиению на 4 четверти и уменьшению площади в два раза). Но можно алгоритм сделать чуть лучше по мат. ожиданию сложности - резать не центральным столбцом, а делать дихотомию по диагонали (из левого верхнего угла). Сложность худшего случая останется такой же (как верно уточнил solacerxt) - O(n+m). Но ожидаемое время работы такого подхода будет O(log(n)*log(m)). Разрез же центральным столбцом ухудшает ожидаемое время работы и приближает его к О(n+m).
Да, это у меня в Гугле спросили на собеседовании. Не решил.
На мой персональный взгляд, это задачка на сообразительность, а не на структуры и алгоритмы.
Мое персональное мнение, что задачи такого типа не подходят для интервью. Объясню. Задачи на сообразительность отбраковывают слишком много хороших кандидатов которые честно готовились и знают достаточно много, но не готовились решать задачи вот конкретно такого типа. Даже можно сообразить про негласную диагональ, но это не является функцией глубины понимания предмета, а чисто функцией натаскивание на решение таких задач.
Успешно работаю у конкурента Гугла много лет, сам проводил множество интервью, знаю, о чем говорю.
Солидарен. Если каждый день такие задачки решать, то мышление подстраивается под это. И в итоге, даже конченный дегенерат сможет такое решать уже просто на автоматизме. Так что, берем в гугл?)
Раньше увлекался головоломками поэтому знакомо
Придумал такое же решение, но начинал с левой стороны, а когда прослушал решение, понял что я сделал лишнее действие - переводил каретку в правую сторону, а потом решал так же как и нужно в лево и в низ.
А почему не сделать бинпоиск по главной диагонали, за log(n) найти пару чисел на главной диагонали (x, y) и (x+1, y+1), между которыми расположено наше и дальше наше искомое число может находиться либо в строке x+1, либо в столбце y+1, и там и там делаем также бинпоиск.
Получается 2 log(n) + log(m), то есть O(log(n) + log(m))
Потому что искомое число может находится справа от столбца y+1 вплоть до последнего, а так же ниже строки x+1 вплоть до самой нижней строки. А значит проверка только строки x+1 и столбца y+1 гарантированно число не найдёт.
Если сделать бинарный поиск по диагонали, можно решить и за O log(n+m).
Не будет такой сложности. В худшем случае так и останется O(n+m). Можно уменьшить ожидаемую сложность, но опять таки не до O(log(n+m)), а до O(log(n)*log(m)).
Видео на паузе. Вот кая я бы попытался решить эту задачу. По условию числа идут по возрастанию. Поиск числа начал с определьния на какой строке и столбце массива находится предполагаемое число, по крайним значениям в строках и столбцах. Далее задачу можно решить или простым перебором всех значений в найденых строке и столбце, или берем значение массива, которое находится посередине найденных строк, столбцов и смотрим. Смотрим где находится наше число, до середины и после. Повторяем эту операцию п-количество раз пока найдем или не найдем нужное нам число.
Решение ещё не слушал, но поиск в ширину со списком очереди напрашивается сам собой. Если первый элемент меньше 14, то добавляем в очередь следующие ячейки по столбцу и строке.
При этом приоритетной должна быть ячейка наиболее близкой к диагонали.
Ребят, берегите время!! Начало: 1:23
Решение пришедшее на ум в первые 30сек. Ищем по диагонали с top left to bottom right. Находим искомое число на диагонали. Если его нет и следующее больше: проверяем только 2 числа: справа от меньшего и слева от большего. И все.
Может где-то и протупил, но по идее должно работать.
Приходит такой чувак устраиваться грузчиком на склад амазон, а ему: реши -ка сначала задачу.