Минимальное Абсолютное Расстояние


Я решил эту проблему

Даны три отсортированный массивы A, B и C не обязательно одинакового размера.

Расчет минимальной абсолютной разности между максимальным и минимальное число из тройки а, B, C, такое что A, B, с принадлежат массивы А, B, C соответственно. т. е. минимизации | Макс(а,б,в) - Мин(А,Б) |.

Пример :

Вход:

А : [ 1, 4, 5, 8, 10 ] Б : [ 6, 9, 15 ] С : [ 2, 3, 6, 6 ]

Выход:

1

Объяснение:

Мы получаем минимальную разницу для А=5, Б=6, с=6, а | Макс(а,б,в) - Мин(А,Б,в) | = |6-5| = 1.

Идея моего решения, если на каждой итерации мы имеем ближайший тройняшки мы сможем получить оптимальный абсолютного минимума.

Я не могу найти чистый способ реализовать такую логику. И мое решение таково.

int Solution::solve(vector<int> &A, vector<int> &B, vector<int> &C) {
    int answer = INT_MAX;
    int a = 0, b = 0, c = 0;
    while(a < A.size() || b < B.size()  || c < C.size() )
    {
        // cout << a << ' ' << b << ' ' << c << endl;
        int MinVal = min(min(A[a], B[b]), C[c]);
        int MaxVal = max(max(A[a], B[b]), C[c]);
        bool na = false, nb = false, nc = false;
        answer = min(answer, abs(MaxVal - MinVal));
        if(a + 1 < A.size() && A[a + 1] <= MaxVal)
        {
            ++a;
        }
        else if(b + 1 < B.size() && B[b + 1] <= MaxVal)
        {
            ++b;
        }
        else if(c + 1 < C.size() && C[c + 1] <= MaxVal)
        {
            ++c;
        }
        else
        {
            // cout << "Next Max\n";
            int next_a = a + 1 < A.size() ? A[a + 1] : INT_MAX;
            int next_b = b + 1 < B.size() ? B[b + 1] : INT_MAX;
            int next_c = c + 1 < C.size() ? C[c + 1] : INT_MAX;
            // cout << next_a << ' ' << next_b << ' ' << next_c << endl;
            if(next_a <= min(next_b, next_c) && next_a != INT_MAX)
            {
                ++a;
            }
            else if(next_b <= min(next_a, next_c) && next_b != INT_MAX)
            {
                ++b;
            }
            else if(next_c < min(next_a, next_b) && next_c != INT_MAX)
            {
                ++c;
            }
            else
            {
                break;
            }

        }
    }
    return answer;
}

Не могли бы вы, пожалуйста, подсказать, как избежать чрезмерного if-else заявления в растворе. Кроме того, это решение не предъявляет больше выбора такой более общий подход будет полезным также



178
1
задан 7 апреля 2018 в 07:04 Источник Поделиться
Комментарии
1 ответ

Заголовки и пространства имен

Нам не хватает заголовков

#include <algorithm>
#include <climits>
#include <cmath>
#include <vector>

Также, похоже, в коде предполагается using namespace std. Приведя все имена из пространства имен является проблематичным; namespace std в частности, так. Посмотрим, почему “использование пространства имен std” считается плохой практикой?.

Код решение и адаптировать его под

Использование Solution класс представляется артефактом вашей тестовой среде. Поскольку функция не нужна ни государству, предпочитают писать его как обычно:

// we'll change this signature later
static int minimum_range(const std::vector<int> &A,
const std::vector<int> &B,
const std::vector<int> &C);

А затем обеспечить Solution как тонкая обертка вокруг него, как:

int Solution::solve(std::vector<int> &A, std::vector<int> &B, std::vector<int> &C) {
return minimum_range(a, b, c);
}

Мы можем тогда назвать minimum_range С нашей тестовой программой намного проще:

int main()
{
return
+ (0 != minimum_range(std::vector{5}))
// add more tests here
+ (1 != minimum_range(std::vector{1, 4, 5, 8, 10}, std::vector{6, 9, 15}, std::vector{2, 3, 6, 6}));
}

Мы могли бы сделать исключение для этого общие рекомендации в случае конкурентоспособность-ориентированного программирования; но затем просмотрите код выходит из окна полностью, а скорость превосходит стиль и ремонтопригодности нет.

Алгоритм

Этот метод в основном звук; он хорошо масштабируется для больших векторов, но плохо масштабируется на множество векторов (как указано в описании).

Для общего кода, предпочитают думать в итераторы , а не индексы. Код будет эквивалентен, но использовать более чем просто векторы и массивы.

Если мы продолжаем набор итераторов (по одному для каждого из массивов), затем на каждом шаге, мы хотим заранее тот, кто указывает на наименьший элемент (дополнительная сложность - нужно тай-брейк, выбрав авансы крайней мере). Мы закончили, когда достигает конца своего выбора; это означает, что мы также должны помнить конечный итератор для каждого массива. Это означает, что мы в конечном итоге сохранение диапазона для каждого входного вектора.

template<typename Iter>
struct range
{
Iter current;
Iter const end;
};

template<typename T>
range<typename std::vector<T>::const_iterator> make_range(const std::vector<T> &v)
{
return {v.begin(), v.end()};
}

Теперь мы можем преобразовать векторы в диапазонах:

static int minimum_range(const std::vector<int> &A,
const std::vector<int> &B,
const std::vector<int> &C)
{
auto range = { make_range(A), make_range(B), make_range(C) };

auto minmax_range = std::minmax_element(range.begin(), range.end());

Для std::minmax_element() позвонила на работу, нам понадобится соответствующий < оператор в нашем ассортименте. Добавить это:

bool operator<(const range& other) const
{
if (current == end) return false;
if (other.current == other.end) return true;
auto a = *current, b = *other.current;
if (a != b) return a < b;

// it's a draw - which one advances least?
if (current+1 == end) return false;
if (other.current+1 == other.end) return true;
a = current[1], b = other.current[1];
return a < b;
}

Теперь давайте вернемся к алгоритму и сделать его итерации:

auto minmax_range = std::minmax_element(r.begin(), r.end());
auto& min_range = minmax_range.first;
auto& max_range = minmax_range.second;
int best = **max_range - **min_range;

while ((++*min_range).current != min_range->end) {
minmax_range = std::minmax_element(r.begin(), r.end());
best = std::min(best, **max_range - **min_range);
if (best == 0) {
break; // we can't improve on zero
}
}

Есть некоторые вещи объяснить было. Мы создаем алиасы для minmax_range, который является парой итераторов range объекты. Мы используем оператор разыменования, которая нуждается в определении в range чтобы дать ток первого элемента диапазона:

auto operator*() const { return *current; }

Контроль цикла начинается с увеличения самой низкой дальности, что требует реализации:

range& operator++() { ++current; return *this; }

Если то, что производится серии, что достиг конца, то мы учли все возможности.

Внутри цикла, мы находим новых мин и Макс (помните, что min_range и max_range еще псевдоним члены minmax_range), и обновление best если требуется.

Расширение для многих входов

Мы можем теперь использовать std::initializer_list чтобы поставить произвольное количество коллекций любого вида (сопоставимых) элемент. Я буду использовать C++17 для этого (так и запишем неявный конструктор rangeиспользование дедукции руководство).

#include <algorithm>
#include <vector>

template<typename Iter>
struct range
{
Iter current;
Iter const end;

template<typename T>
range(const T& v)
: current{v.begin()},
end{v.end()}
{
}

explicit operator bool() const { return current != end; }

auto operator*() const { return *current; }

range& operator++() { ++current; return *this; }

bool operator<(const range& other) const
{
return *this && (!other || *current < *other.current);
}
};

// deduction guide
template<typename Container>
range(Container c) -> range<typename Container::const_iterator>;

template<typename Iter>
static auto minimum_range(std::initializer_list<range<Iter>> containers)
{
using std::begin;
using std::end;

// Copy initializer list to read/write container
std::vector r(begin(containers), end(containers));

auto minmax_range = std::minmax_element(begin(r), end(r));
auto& min_range = minmax_range.first;
auto& max_range = minmax_range.second;
auto best = **max_range - **min_range;

while (++*min_range) {
minmax_range = std::minmax_element(begin(r), end(r));
best = std::min(best, **max_range - **min_range);
}

return best;
}

// convert containers to ranges and forward
template<typename... Args>
static auto minimum_range(const Args&... args)
{
return minimum_range({range(args)...});
}

#include <list>
int main()
{
return
+ (0 != minimum_range(std::list{5}))
+ (0.5 != minimum_range(std::vector{0.0}, std::vector{0.0}, std::vector{0.5}))
+ (6 != minimum_range(std::vector{6,30}, std::vector{10,12}, std::vector{6,15,30}, std::vector{12}))
+ (1 != minimum_range(std::vector{0, 6, 10}, std::vector{5}, std::vector{5}))
// add more tests here
+ (1 != minimum_range(std::list{1, 4, 5, 8, 10}, std::list{6, 9, 15}, std::list{2, 3, 6, 6}));
}

Мне не удалось создать тест, который доказывает необходимость тай-брейк в operator<так я убрал этот код. Я должен был написать это, в первую очередь, без тест для тренировки, конечно...

2
ответ дан 9 апреля 2018 в 06:04 Источник Поделиться