Два указателя в JavaScript

Проблем

Подаръчната карта и всички двойки

Клиентът има подаръчна карта и иска да я похарчи до цент: два продукта, които заедно струват точно колкото картата. Сайтът ги търси с два вложени цикъла, като проверява всяка двойка:

let checks = 0;

function allPairs(prices, card) {
  for (let i = 0; i < prices.length; i++) {
    for (let j = i + 1; j < prices.length; j++) {
      checks++;
      if (prices[i] + prices[j] === card) {
        return [i, j];
      }
    }
  }
  return null;
}

Ценоразписът е 1000 продукта по 2, 4, …, 2000 €, а картата е за 2001 €. Сборът на две четни цени никога не е нечетен, значи двойка няма. Това е най-лошият случай: циклите стигат до края.

const n = 1000;
const prices = Array.from({ length: n }, (_, i) => 2 * (i + 1));
const card = 2 * n + 1;
const pair = allPairs(prices, card);
console.log("Двойка: " + (pair === null ? "няма" : "има"));
console.log(`Проверки: ${checks}`);

Двойка: няма
Проверки: 499500

Почти половин милион проверки за 1000 продукта. Двойките са n(n − 1) / 2, затова това е O(n²): при 100 000 продукта стават около 5 милиарда.

А ценоразписът е подреден по цена, и циклите не се възползват от това.

Идеята

Единият отляво, другият отдясно

Сложи един пръст на най-евтината цена, а друг на най-скъпата. Пръстите са индекси: lo и hi. Събери двете цени:

ако сборът е колкото картата, готово;
ако е малко, евтината цена отпада: дори с най-скъпата, която още е в играта, не стига. lo отива една цена надясно;
ако е много, скъпата отпада: тя е много дори с най-евтината. hi отива една цена наляво.

Всяка стъпка изхвърля една цена завинаги, и никоя двойка с отговора не се губи. Когато lo и hi се срещнат, цените са свършили. Най-много n − 1 стъпки: O(n).

Това се казва два указателя (two pointers): два индекса, които вървят по масива, а всяко сравнение казва кой от тях да мръдне. Тук те вървят един към друг. Познаваш идеята от двоичното търсене, където lo и hi пазят обхвата. Там всяка проба изхвърля половината, тук изхвърля една цена.

Условието е същото: масивът трябва да е подреден. Само тогава „надясно е по-скъпо“ е вярно.

Виж го

lo и hi в ценоразписа

function findPair(prices, card) {
  let lo = 0;
  let hi = prices.length - 1;
  while (lo < hi) {
    const sum = prices[lo] + prices[hi];
    if (sum === card) {
      return [lo, hi];
    } else if (sum < card) {
      lo++;
    } else {
      hi--;
    }
  }
  return null;
}

const prices = [3, 5, 8, 12, 15, 19, 24, 27, 31, 36];
const pair = findPair(prices, 50);
if (pair === null) {
  console.log("Няма двойка за 50 €");
} else {
  const [lo, hi] = pair;
  console.log(`${prices[lo]} € + ${prices[hi]} €`);
}

19 € + 31 €

function findPair(prices, card) {
  let lo = 0;
  let hi = prices.length - 1;
  while (lo < hi) {
    const sum = prices[lo] + prices[hi];
    if (sum === card) {
      return [lo, hi];
    } else if (sum < card) {
      lo++;
    } else {
      hi--;
    }
  }
  return null;
}

Стъпка по стъпка, с думи

Ценоразписът е подреден: 10 цени. Картата е 50 €. lo е на най-евтината цена, hi на най-скъпата.
3 € + 36 € = 39 € < 50 €: малко е. На 3 € не стига дори най-скъпата цена, значи 3 € отпада: lo отива надясно.
5 € + 36 € = 41 € < 50 €: малко е. На 5 € не стига дори най-скъпата цена, значи 5 € отпада: lo отива надясно.
8 € + 36 € = 44 € < 50 €: малко е. На 8 € не стига дори най-скъпата цена, значи 8 € отпада: lo отива надясно.
12 € + 36 € = 48 € < 50 €: малко е. На 12 € не стига дори най-скъпата цена, значи 12 € отпада: lo отива надясно.
15 € + 36 € = 51 € > 50 €: много е. С 36 € е много дори с най-евтината цена, значи 36 € отпада: hi отива наляво.
15 € + 31 € = 46 € < 50 €: малко е. На 15 € не стига дори най-скъпата цена, значи 15 € отпада: lo отива надясно.
19 € + 31 € = 50 €: точно колкото картата. findPair връща индексите 5 и 8.
7 сбора вместо 45 двойки. Всяка стъпка изхвърля една цена завинаги, затова стъпките са най-много n − 1.

Функцията връща масив с двата индекса, а когато двойка няма, null. const [lo, hi] = pair ги разделя.

По-точно, за любопитните

Защо не се губи двойка. Да кажем, че отговорът е двойката на индекси i и j, i < j. Докато lo ≤ i и hi ≥ j, указателите не могат да прескочат отговора:

ако lo < i, сборът на lo и hi е най-много сборът на i и hi. Ако е малко, lo с право отива надясно, без да мине i;
ако hi > j, по същия начин hi с право отива наляво, без да мине j.

Когато lo стигне i и hi стигне j, сборът е точно картата. Ако двойките са няколко, указателите намират най-външната: тази с най-евтината цена.

Пробвай

Предвиди коя двойка

Картата е 43 €. В ценоразписа има две двойки с такъв сбор: 12 € + 31 € и 19 € + 24 €. Какво печата програмата?

function findPair(prices, card) {
  let lo = 0;
  let hi = prices.length - 1;
  while (lo < hi) {
    const sum = prices[lo] + prices[hi];
    if (sum === card) {
      return [lo, hi];
    } else if (sum < card) {
      lo++;
    } else {
      hi--;
    }
  }
  return null;
}

const prices = [3, 5, 8, 12, 15, 19, 24, 27, 31, 36];
const pair = findPair(prices, 43);
if (pair === null) {
  console.log("Няма двойка за 43 €");
} else {
  const [lo, hi] = pair;
  console.log(`${prices[lo]} € + ${prices[hi]} €`);
}

Отговор

19 € + 24 €

Няма двойка за 43 €

12 € + 31 €

Пробвай

Попълни

Сборът е по-малък от картата. Кой указател мърда и накъде?

function findPair(prices, card) {
  let lo = 0;
  let hi = prices.length - 1;
  while (lo < hi) {
    const sum = prices[lo] + prices[hi];
    if (sum === card) {
      return [lo, hi];
    } else if (sum < card) {
      ;
    } else {
      hi--;
    }
  }
  return null;
}

Пробвай

Намери грешката

Картата е 50 €, а 19 € + 31 € е в ценоразписа. Функцията казва, че двойка няма:

const prices = [3, 5, 8, 12, 15, 19, 24, 27, 31, 36];
const pair = findPair(prices, 50);
if (pair === null) {
  console.log("Няма двойка за 50 €");
} else {
  const [lo, hi] = pair;
  console.log(`${prices[lo]} € + ${prices[hi]} €`);
}

Няма двойка за 50 €

Избери реда с грешката.

Виж го

Колко стъпки

Същият ценоразпис от 1000 продукта и картата за 2001 €, а функцията брои стъпките на цикъла:

let steps = 0;

function findPair(prices, card) {
  let lo = 0;
  let hi = prices.length - 1;
  while (lo < hi) {
    steps++;
    const sum = prices[lo] + prices[hi];
    if (sum === card) {
      return [lo, hi];
    } else if (sum < card) {
      lo++;
    } else {
      hi--;
    }
  }
  return null;
}

const n = 1000;
const prices = Array.from({ length: n }, (_, i) => 2 * (i + 1));
const card = 2 * n + 1;
const pair = findPair(prices, card);
console.log("Двойка: " + (pair === null ? "няма" : "има"));
console.log(`Стъпки: ${steps}`);

Двойка: няма
Стъпки: 999

999 стъпки вместо 499 500 проверки. Двете функции дават един и същ отговор, а при 100 000 продукта разликата е 99 999 стъпки срещу около 5 милиарда.

Пусни ги в браузъра. Третата крива е за неподреден ценоразпис: първо merge sort, после двата указателя.

Всички двойки O(n²)
Два указателя (подреден списък) O(n)
Подреди, после два указателя O(n log n)

Алгоритъм	n = 10	n = 1000	n = 10 000	n = 100 000
Всички двойки	45	499 500	49 995 000	≈ 4 999 500 000
Два указателя (подреден списък)	9	999	9999	99 999
Подреди, после два указателя	31	9692	130 424	1 636 539

Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.

function findPair(prices, card) {
  let lo = 0;
  let hi = prices.length - 1;
  while (lo < hi) {
    const sum = prices[lo] + prices[hi];
    if (sum === card) {
      return [lo, hi];
    } else if (sum < card) {
      lo++;
    } else {
      hi--;
    }
  }
  return null;
}

Всички двойки над 10 000 не пускаме: те са ≈. Подреждането струва повече от самите указатели, но кривата му е O(n log n) и пак е далеч под O(n²).

Идеята

Подреден ли е списъкът

Двата указателя искат подреден масив. Когато не е:

Подреди първо. Подреждането е O(n log n), указателите O(n), общо O(n log n). При 100 000 цени това са около 1,6 милиона операции срещу около 5 милиарда. Подреждането печели почти винаги.
Ако търсиш много пъти в същия списък (всеки клиент с различна карта), подреждаш веднъж, и всяко търсене после е O(n).
Индексите се сменят. След подреждане prices[5] вече не е петият продукт от каталога. Ако ти трябват продуктите, подреди двойки (цена, продукт) или обекти по цена.

const prices = [27, 3, 36, 15, 8, 31, 19, 5, 24, 12];
prices.sort((a, b) => a - b);
console.log("[" + prices.join(", ") + "]");
const pair = findPair(prices, 50);
if (pair === null) {
  console.log("Няма двойка за 50 €");
} else {
  const [lo, hi] = pair;
  console.log(`${prices[lo]} € + ${prices[hi]} €`);
}

[3, 5, 8, 12, 15, 19, 24, 27, 31, 36]
19 € + 31 €

sort() в JavaScript без функция за сравнение подрежда числата като текст: „12“ е преди „3“, защото „1“ е преди „3“. За числа винаги подаваш (a, b) => a - b. Без нея двата указателя тръгват по грешен ред и пропускат двойки:

const prices = [27, 3, 36, 15, 8, 31, 19, 5, 24, 12];
prices.sort();
console.log("[" + prices.join(", ") + "]");

[12, 15, 19, 24, 27, 3, 31, 36, 5, 8]

Има и начин без подреждане: минаваш веднъж по цените и пазиш видените в множество. За всяка цена питаш дали картата − цената вече е видяна. Това е O(n) средно, с hash таблица и с n допълнителна памет. Двата указателя са без допълнителна памет, но искат подреден масив.

Виж го

Същата идея: сливане и повторения

Двата указателя не винаги вървят един към друг. Понякога вървят в една посока.

Сливане на два подредени списъка. Поръчките от сайта и от телефона са номерирани от един брояч, но се пазят поотделно, всеки списък подреден. Отчетът за деня иска един подреден списък. i върви по първия, j по втория, и всеки път по-малкият номер отива в резултата. Това е сливането от merge sort:

function merge(a, b) {
  const result = [];
  let i = 0;
  let j = 0;
  while (i < a.length && j < b.length) {
    if (a[i] <= b[j]) {
      result.push(a[i++]);
    } else {
      result.push(b[j++]);
    }
  }
  while (i < a.length) {
    result.push(a[i++]);
  }
  while (j < b.length) {
    result.push(b[j++]);
  }
  return result;
}

const web = [1003, 1007, 1012, 1020];
const phone = [1001, 1009, 1010, 1031, 1044];
console.log("[" + merge(web, phone).join(", ") + "]");

[1001, 1003, 1007, 1009, 1010, 1012, 1020, 1031, 1044]

Повторенията на място. Цените от импорта са подредени, но с повторения, а филтърът трябва да покаже всяка цена веднъж. read чете всяка цена, а write е мястото на следващата нова. Всичко преди write е готово и без повторения:

function unique(prices) {
  if (prices.length === 0) {
    return 0;
  }
  let write = 1;
  for (let read = 1; read < prices.length; read++) {
    if (prices[read] !== prices[write - 1]) {
      prices[write] = prices[read];
      write++;
    }
  }
  return write;
}

const prices = [5, 5, 8, 12, 12, 12, 19, 24, 24];
const k = unique(prices);
prices.length = k;
console.log(`Различни цени: ${k}`);
console.log("[" + prices.join(", ") + "]");

Различни цени: 5
[5, 8, 12, 19, 24]

Масивът в JavaScript може да се скъси на място: prices.length = k маха всичко след първите k.

И двете са O(n): всеки указател минава по веднъж.

Виж го

Огледален промокод

Кампанията „Огледален код“ приема само промокодове, които се четат еднакво от двете страни. Указателите тръгват от двата края и сравняват знак по знак, докато се срещнат:

function isMirror(code) {
  let lo = 0;
  let hi = code.length - 1;
  while (lo < hi) {
    if (code[lo] !== code[hi]) {
      return false;
    }
    lo++;
    hi--;
  }
  return true;
}

console.log(isMirror("AB7CC7BA"));
console.log(isMirror("AB7CD7BA"));

true
false

По-точно, за любопитните

Същото се пише и на един ред, като сравниш кода с обърнато копие:

const code = "AB7CC7BA";
console.log(code === [...code].reverse().join(""));

true

[...code].reverse().join("") прави масив от знаците, обръща го и го събира в нов низ.

Отговорът е същият и пак е O(n). Разликата: копието е още n знака памет и винаги се прави цялото, а указателите спират на първата разлика. За промокод от 8 знака това е без значение. За проверка на милиони редове в лог вече има значение.

Със същите указатели се обръща масив на място: размени lo и hi, мръдни ги навътре.

Упражнение

Най-близо до картата

Реши задачата в редактора си.

Най-близо до картата. Точна двойка невинаги има. Тогава магазинът предлага двата продукта, които заедно са най-близо до картата, без да я надминат. Ценоразписът е 3, 5, 8, 12, 15, 19, 24, 27, 31 и 36 €, картата е 45 €. С двата указателя: ако сборът е до картата, запомни го, ако е по-добър от досегашния, и мръдни lo. Иначе мръдни hi.

Най-близо до 45 €: 8 € + 36 € = 44 €

Още задачи

Огледален код с тирета. Промокодовете се печатат с тирета: AB7-CC-7BA. Пропускай тиретата: всеки указател ги прескача, преди да сравнява.
По две на курс. Пратките са подредени по тегло, а един курс носи най-много две пратки до 30 кг общо. Колко курса трябват най-малко? Сложи най-леката с най-тежката, ако се събират, иначе най-тежката тръгва сама.
Общи продукти. Два подредени списъка с номера на продукти: от склада и от поръчката. Намери кои номера има и в двата, с два указателя в една посока.

Тест

Провери се

1. Ценоразписът е подреден. lo е на 8 €, hi на 36 €, картата е 50 €. Сборът е 44 €. Какво правиш?Връщаш се към началотоhi отива налявоlo отива надясно: 8 € не стига дори с най-скъпата цена

2. Ценоразписът има 100 000 продукта, а двойка за картата няма. Колко сбора смятат двата указателя?Около 5 милиарда99 999Около 17, колкото двоичното търсене

3. Списъкът с цени не е подреден. Кое е най-бързото от трите?Всички двойки (O(n²)), защото подреждането струваПодреждаш (O(n log n)) и пускаш двата указателя (O(n))Двата указателя направо върху неподредения списък

4. Премахваш повторенията от подредения списък на място, с read и write. Кое е вярно?read минава по всеки елемент, а write показва докъде е готовата частТрябва нов списък със същата дължинаread и write вървят един към друг от двата края

5. Защо проверката на огледален промокод с два указателя е по-добра от сравнението с обърнато копие?Не прави копие и спира при първата разликаОбърнатото копие дава грешен отговорТя е O(log n)

Два указателя

Бисквитки