0

Есть эталонный массив, с правильной сортировкой. Выбрал именно вес для наглядности.

[
    "тонна",
    "центнер",
    "килограмм",
    "фунт",
    "грамм",
    "миллиграмм"
]

И есть другие массивы, сортировку которых нужно проверить.

Нужно написать функцию, которая принимает массив, сравнивает его сортировку с эталонным массивом, и возвращает boolean - правильная сортировка или нет.

этот массив с правильной сортировкой

[
   "тонна",
   "грамм",
   "миллиграмм""
]

этот с НЕ правильной

[
    "грамм",
    "тонна",
    "миллиграмм"
]

этот массив с правильной сортировкой хотя МИКРОграммов нет в эталонном массиве, если неизвестные значения находятся в конце массива то их можно упустить

[
    "тонна",
    "центнер",
    "МИКРОграмм"
]

этот с НЕ правильной МИКРОграммы в начале массива или в середине

[
    "МИКРОграмм",
    "тонна",
    "центнер",
]

[
    "тонна",
    "МИКРОграмм",
    "центнер",
]

вот такая вот задачка, кажется что с собеседования, но уверяю что это реальный проект.

Написал такое решение

 public function checkSort(array $array, array $referenceArray)
    {
        $indexes = [];
        $prevIndex = null;

        // создадим новый массив, и заполним его индексами найденных значений из эталонного массива
        foreach ($array as $item) {
            $index = array_search($item, $referenceArray, true);

            $curIndex = $index === false ? -1 : $index;

            // -1 это элемент которого нет в эталонном массиве
            // если после -1 идет "нормальный" индекс - то массив сразу не правильно отсортирован
            // после -1 не должны идти индексы
            if ($prevIndex === -1 && $curIndex > -1) {
                return false; // сортировка НЕ верна
            }

            $prevIndex = $curIndex;

            $indexes[] = $curIndex;
        }

        // удаляем с массива все -1
        $indexes = array_filter($indexes, function ($item) {
            return $item > -1;
        });

        // у нас остались только правильные индексы, нужно проверить что они идут подряд
        // например должно быть как то так - [6, 7, 8], [3, 4, 5], [6, 7, 7, 8] (да, дубли тоже могут быть)
        // а вот так не правильно [6, 8, 7], [5, 4, 3], [5, 3, 4]
        $prevItem = 0;

        foreach ($indexes as $item) {
            if ($item >= $prevItem) {
                $prevItem = $item;
            } else {
                return false; // сортировка НЕ верна
            }
        }

        return true; // сортировка верна
    }
2
  • "если неизвестные значения находятся в конце массива то их можно упустить" - а если вместо МИКРОграмма МЕГАтонна? 1 янв в 19:37
  • Не имеет значения, все что не входит в эталонный массив можно размещать только в конце массива, в любых количествах. Начало и середина - нельзя.
    – Norris
    1 янв в 19:41

1 ответ 1

1

Как сказал кто-то и когда-то, всё гениальное просто (:

<?php
function test($array1, $array2) {
    $last_pos = -1;
    for ($index = 0; $index < count($array2); $index++) {
        $pos = array_search($array2[$index], $array1);
        if (($pos !== false && $last_pos === false) || ($pos !== false && $last_pos >= $pos))
            return false;
        $last_pos = $pos;
    }
    return true;
}
$array = [
    "тонна",
    "центнер",
    "килограмм",
    "фунт",
    "грамм",
    "миллиграмм"
];
var_dump(test($array, [
    "тонна",
    "грамм",
    "миллиграмм"
])); // bool(true)
var_dump(test($array, [
    "грамм",
    "тонна",
    "миллиграмм"
])); // bool(false)
var_dump(test($array, [
    "тонна",
    "центнер",
    "МИКРОграмм"
])); // bool(true)
var_dump(test($array, [
    "МИКРОграмм",
    "тонна",
    "центнер"
])); // bool(false)
?>
1
  • @АлексейР, согласен, сейчас изменю ответ 3 янв в 13:56

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.