Комментарии 49
В 4 пункте ошибка, у вас вызов Array.prototype.include происходит внутри цикла, а значит там будет O(N*(N-1)) ~ O(N^2). Улучшение ничем не лучше первого варианта с полным перебором, но при этом добавили кучу доступов к памяти
1.
Это очень правильно с житейской точки зрения перепроверить входные данные, но академические задачи на то и академические что исходные условия не подвергаются сомнению.
Постановка задачи2.
Нам дают упорядоченный массив...
Но кто даст гарантию, что массив был упорядоченным?
Это очень правильно с житейской точки зрения перепроверить входные данные, но академические задачи на то и академические что исходные условия не подвергаются сомнению.
Чтобы в четвертом варианте было O(N), searchValues переменная должна быть hash map.
решал похожую задачу на джаве, по ТЗ массив не был отсортирован.
мой вариант был — берем хэшмапу, число в исходном массиве — это ключ в ней, значение 1 (тру, по вкусу).
потом идем по исходному массиву и смотрим, есть ли единичка в мапе под ключем [искомое — текущее]. если да — то ура, нашли пару. если нет — идем дальше. если дошли до конца и пар не нашли — значит, их нет.
итого — 2 линейных прохода по исходному массиву. доступ в хэшмапе константный.
мой вариант был — берем хэшмапу, число в исходном массиве — это ключ в ней, значение 1 (тру, по вкусу).
потом идем по исходному массиву и смотрим, есть ли единичка в мапе под ключем [искомое — текущее]. если да — то ура, нашли пару. если нет — идем дальше. если дошли до конца и пар не нашли — значит, их нет.
итого — 2 линейных прохода по исходному массиву. доступ в хэшмапе константный.
Именно так :) Ниже пример решения, если попросят в усложнение вывести индексы этих элементов
var twoSum = function(nums, target) {
const hash = [];
for (let i = 0; i < nums.length; i++) {
if (hash[nums[i]] !== undefined) {
hash[nums[i]].push(i);
} else {
hash[nums[i]] = [i];
}
const hashBucket = hash[target - nums[i]];
if (hashBucket !== undefined) {
if (i !== hashBucket[0]) {
return [i, hashBucket[0]]
} else if (hashBucket[1] !== undefined) {
return [i, hashBucket[1]];
}
}
}
};
Доступ в хэшмапе константный, но долгий (рандомное обращение к памяти). А в quicksort добавляется логарифм, но функция эффективно работает с памятью (все проходы идут по порядку массива). Что быстрее, не знаю.
С точки зрения «банальной эрудиции» можно «доработать» брутфорс.
1. Разделить исходный массив на четные и нечетные.
2. Если искомое число четное то оно может быть получено либо сложением Ч+Ч либо Н+Н, а нечетное м.б. получено сложением Ч+Н
Понятное дело все зависит от того чем наполнен исходный массив но при нормальном распределении такое упрощение имеет смысл. Если почесать репу то можно, наверное, вывести еще несколько критериев упрощения.
Все зависит от того что хотят видеть на интервью — набор готовых стандартных решений либо мыслительный процесс.
1. Разделить исходный массив на четные и нечетные.
2. Если искомое число четное то оно может быть получено либо сложением Ч+Ч либо Н+Н, а нечетное м.б. получено сложением Ч+Н
Понятное дело все зависит от того чем наполнен исходный массив но при нормальном распределении такое упрощение имеет смысл. Если почесать репу то можно, наверное, вывести еще несколько критериев упрощения.
Все зависит от того что хотят видеть на интервью — набор готовых стандартных решений либо мыслительный процесс.
Лично я невысоко ценю подобные неасимптотические «креативные» отпимизации. В задаче не было речи ни о каком распределении, да и накладных расходов от такого разделения слишком много, проще уже нормальное решение написать.
Ну и в добавок в первом цикле можно проверять (если массив отсортирован)
и не крутить лишний раз цикл если число в массиве больше чем искомое…
if (arr[i] > val) break;и не крутить лишний раз цикл если число в массиве больше чем искомое…
Не стоит противопоставлять готовые знания и умение думать. Да, бинпоиск/метод двух указателей это стандартная идея. Но чтобы воткнуть их, иногда нужно сильно подумать)
А зачем вообще при брутфорсе перебирать второй цикл каждый раз с нуля, ведь все элементы до i мы уже проверили. И последнее решение с дополнительной памятью бы работало если бы использовали хеш
Плюс в задаче не уточняется, что это может быть один (или не может) и тот-же индекс и тогда [1, 2, 4, 9] для результата 8 вернет true потому как 4+4=8. Как обычно "академические задачи" страдают неточностью в условиях. Типа "Для простоты примем, что число пи равно трем."
Ну и решение зависит от размеров массива, текущей располагаемой (предполагаемой) средой исполнения и т.д. Где-то тупой перебор, где-то на подмассивы бить, где-то бинарщина во все поля...
в 3 вариант можно добавить:
— сложить первые 2 числа и если сумма больше искомого — false
— пока последнее число больше искомого — end--
Ну а дальше алгоритм как есть
— сложить первые 2 числа и если сумма больше искомого — false
— пока последнее число больше искомого — end--
Ну а дальше алгоритм как есть
А в третьем варианте разве мы не получим O(N^2) и дополнительный расход памяти, так как на каждой итерации мы будем копировать исходный массив? Не лучше ли было адаптировать бинарный поиск, чтобы он пропускал элемент, для которого мы производим поиск?
НЛО прилетело и опубликовало эту надпись здесь
Не понимаю прикладного характера задачи, но при малых массивах (до миллиона) может оказаться, что простой перебор работает быстрее, чем время подготовки специальных структур, типа деревьев или сортировка. Логарифм на определенном диапазоне больше, чем квадрат х. Лучше сесть с таймером и сделать таблицу времени на каждый алгоритм с разными объемами данных.
Только это граница — не миллион, а от силы 1000. Попробуйте сдать лобовое решение, например, сюда: https://informatics.mccme.ru/mod/statements/view.php?id=597
При решении реальных задач теория работает частично. Объективный показатель — время исполнения. Может оказаться, что массив постоянно меняется и тогда нужен будет другой подход.
Если реальная задача свелась к академической (типа поиск минимума на отрезках массива, поиск двух элементов с заданной суммой, поиск наибольшего непересекающегося подмножества ребер графа и так далее), то теория там работает хорошо)) Я ни разу еще не слышал, чтобы на 1е6 заходил квадрат. Асимпотика позволяет предсказывать, сработает ли код на входных данных того или иного размера, с довольно хорошей точностью.
И тот факт, что через неделю ТЗ может как-то поменяться, кмк не мешает здесь и сейчас написать эффективный код. Ну или не написать, но аргументированно))
В таком случае можно использовать сразу две реализации: простая для малых массивов, и сложная для больших.
Берем первое число массива. Находим 2 соседних числа массива такие, что a[1]+a[j]<x a[1]+a[j+1]>x. Возможно, будет одно такое число. Следующее число массива. Используем полученные числа как начальный район поиска. И так далее.
Скорость О(N), память О(1).
Скорость О(N), память О(1).
Трудности перевода — «space complexity» и «time complexity» переводятся как «сложность по памяти» и «сложность по времени». Пожалуйста, при переводе статей учитывайте терминологию русского языка, становится гораздо приятнее читать.
А какая тут сложность получается?
var arr = [-22,-9,-4,2,5,7,8,9,11,12,16,17,21,22,25,26,29];
for(let i=30; i > 0; i--) {
console.log(`${i} = ${search(arr, i)}`);
}
function search(arr, num) {
var filterRange = arr[0] < 0 ? num - arr[0] : num;
var new_arr = arr.filter(i=>{ return i <= filterRange })
for(var i = new_arr.length; i >= 0; i--) {
var para = Number(num) - Number(new_arr[i]);
if (new_arr.includes(para)) {
return [ new_arr[i], para ];
break;
}
}
return false;
}
Интересно, а насколько затратна в Javascript вся эта операция удаления элемента из массива и передачи нового массива в функцию во 2 решении?
function findPairOfAddendsBySum (array, requiredSum)
{
let lower = 0
let upper = array.length - 1
while (lower < upper)
{
const currentSum = array[lower] + array[upper]
const middle = Math.floor(lower + (upper - lower) / 2)
if (currentSum < requiredSum)
{
if (array[middle] + array[upper] < requiredSum)
lower = middle;
++lower
}
else if (currentSum > requiredSum)
{
if (array[lower] + array[middle] > requiredSum)
upper = middle;
--upper
}
else
{
return [array[lower], array[upper]]
}
}
return []
}В лучшем случае алгоритм аналогичен двоичному поиску O(log n), в худшем — O(n)
skillbox пожалуйста обновите статью. Решение задачи 4 содержит ошибку: если у вас решением задачи будут 2 последних элемента массива, то мы также как и в 1м случае получим O(N^2)
Ошибка в оригинальной статье (это перевод), поэтому лучше было бы указать на ошибку там. Что я и сделал: medium.com/@boriscoder/329409e9fc5
Хм, вроде решил. Сложность O(n) в худшем случае, память O(1).
Попробовать можно тут.
function solve(target, arr) {
let i = 0;
let j = arr.length - 1;
while (i < j) {
const sum = a[i] + a[j];
if (sum < target) {
++i;
} else if (target < sum) {
--j;
} else {
return true;
}
}
return false;
}
const target = 8;
let a = [];
// a = [1, 2, 3];
a = [1, 2, 2, 4, 4];
console.log(
solve(target, a)
);
Попробовать можно тут.
На самом деле, есть решение для неупорядоченного массива через черпачную сортировку, о которой, крайне незаслуженно, многие забывают, которое работает за O(n) и требует O(n) памяти и читает память практически линейно на больших массивах, пишет не совсем линейно, но в крайне ограниченное число адресов (в примере ниже — 256), т.е. почти все записи попадают в кэш.
Единственное ограничение, которое он накладывает — значения массива должны быть ограничены сверху некоторой константой. При этом алгоритм по сложности очень толерантен к данной константе.
Единственное ограничение, которое он накладывает — значения массива должны быть ограничены сверху некоторой константой. При этом алгоритм по сложности очень толерантен к данной константе.
Вот пример для массива с long значениями
// assumption: 0 <= array values < 2^63 (8 bytes signed)
// complexity: O(n)
// memory: O(n)
function solve(arr, target) {
// magic is here
bucketSort(arr);
// classic O(n) solution for sorted array
var i = 0;
var j = arr.length - 1;
var sum;
while (i < j) {
const sum = arr[i] + arr[j];
if (sum < target) {
i++;
} else if (target < sum) {
j--;
} else {
return true;
}
}
return false;
}
// bucket sort has complexity O(n) and memory consumption O(n) for array of values less than constant
function bucketSort(arr) {
var buckets, i, j, byteShift, bucketId, pos;
// create empty buckets
buckets = []; // will consume no more than O(n) memory
for (i = 0; i < 256; i++) {
buckets[i] = [];
}
// sort
for (byteShift = 0; byteShift < 8; byteShift++) {
// init buckets
for (i = 0; i < 256; i++) {
buckets[i].length = 0; // lets reuse memory
}
// split array to buckets
for (i = 0; i < arr.length; i++) {
bucketId = (arr[i] >>> (byteShift * 8)) & 255;
buckets[bucketId].push(arr[i]);
}
// merge buckets to array
pos = 0;
for (i = 0; i < 256; i++) {
for (j = 0; j < buckets[i].length; j++) {
arr[pos] = buckets[i][j];
pos++;
}
}
}
}
В реальности эти алгоритмы должны работать не с числами и индексами. Стоимость каждой операции нужно выяснять. Без этого, не надо морочить голову переусложнённым кодом. Брутфорс, немного оптимизированный, самый годный вариант.
А почему так нельзя? Тесты вроде проходит
const findSum = (arr, summ) => {
for (let i = 0; i < arr.length; i++) {
let c = arr.indexOf(summ - arr[i]);
if (c > -1 && c != i) return true;
}
return false;
}
const findSum = (arr, val) => {
for (let i = 0; i < arr.length; i++) {
for (let j = i+1; j < arr.length; j++) {
if (arr[i] + arr[j] === val) {
return true;
};
};
};
return false;
};
как по мне это самое оптимальное решение так как не происходит повторное сравнивание чисел простого массива
Какие недостатки у этого решения, кроме того что можно some на for заменить?
function findSum(arr, number) {
return arr.some((element, index) => {
return arr.includes(number - element, index + 1);
});
}
Господа, не усложняйте )
function searcher(haystack,needle){
let prev = null;
let acc = [];
for(let item of haystack){
if(!prev){
prev = item;
continue;
}
if(needle < item){
continue;
}
if(needle == item + prev ){
acc.push([prev,item]);
}
prev = item;
}
return acc;
}
let haystack = [1, 2, 4, 4];
let needle = 8;
console.log(searcher(haystack,needle));
Еще по брутофорсу:
const findSum = (arr, val) => {
for (let i = 0; i < arr.length - 1; i++) {
for (let j = i + 1; j < arr.length; j++) {
if (arr[i] + arr[j] === val) {
return true;
};
};
};
return false;
};
Что-то все так сложно написано, поэтому читал «наискосок». Такой вариант решения задачи был?
const arr = [1, 2, 4, 4];
const value = 8;
function check(arr){
let flag = false;
for (let i=0; i<(arr.length/2+1); i++){
const item = arr[i];
const dif = value — item;
if (arr.includes(dif)){
flag = true;
break;
}
}
return flag;
}
console.log(check(arr))
const arr = [1, 2, 4, 4];
const value = 8;
function check(arr){
let flag = false;
for (let i=0; i<(arr.length/2+1); i++){
const item = arr[i];
const dif = value — item;
if (arr.includes(dif)){
flag = true;
break;
}
}
return flag;
}
console.log(check(arr))
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Решаем задачу из интервью Google на JavaScript: 4 разных способа