Определите индекс, соответствующий наименьшим данным в наборе массивов

Question

Я считаю, что это тривиальный алгоритмический вопрос, но я, похоже, не смог найти эффективного и элегантного решения.

У нас есть 3 массива типа int (Aa, Ab, Ac) и 3 курсора (Ca, Cb, Cc), которые указывают индекс в соответствующем массиве.Я хочу определить и увеличить курсор, указывающий на наименьшее значение.Если этот курсор уже находится в конце массива, я исключу его и увеличу курсор, указывающий на второе наименьшее значение.Если есть только один курсор, который не находится в конце массива, мы увеличиваем его.

Единственные решения, которые я могу придумать, являются сложными и / или неоптимальными.Например, я всегда получаю огромное, если ... еще ...

Кто-нибудь видит четкое решение этой проблемы?

Я программирую на C ++, но не стесняюсь обсуждатьэто в псевдокоде или на любом другом языке.

Спасибо

Answer 1

Псевдо-Java-код:

int[] values = new int[3];
values[0] = aa[ca];
values[1] = ab[cb];
values[2] = ac[cc];
Arrays.sort(values);

boolean done = false;
for (int i = 0; i < 3 && !done; i++) {
    if (values[i] == aa[ca] && ca + 1 < aa.length) {
        ca++;
        done = true;
    }
    else if (values[i] == ab[cb] && cb + 1 < ab.length) {
        cb++;
        done = true;
    }
    else if (cc + 1 < ac.length) {
        cc++;
        done = true;
    }
}
if (!done) {
    System.out.println("cannot increment any index");
    stop = true;
}

По существу, он делает следующее:

1. инициализирует массив values с aa[ca], ab[cb]и ac[cc]

2. сортировка values

3. сканирование values и приращение, если возможно (т.е. еще не в конце массива) индекс соответствующего значения

Я знаю, сортировка в лучшем случае O (n lg n), но я сортирую только массив из 3 элементов.

Answer 2

Псевдокод: РЕДАКТИРОВАТЬ: немного прибрался

class CursoredArray
{
    int index;
    std::vector<int> array;

    int val()
    {
        return array[index];
    }

    bool moveNext()
    {
        bool ret = true;
        if( array.size() > index )
            ++index;
        else
            ret = false;
        return ret;
    }   
}    

std::vector<CursoredArray> arrays;
std::vector<int> order = { 0, 1, 2 };//have a default order to start with

if( arrays[0].val() > arrays[1].val() )
    std::swap( order[0], order [1] );

if( arrays[2].val() < arrays[order[1]].val() )//if the third is less than the largest of the others
{
    std::swap( order[1], order [2] );
    if( arrays[2].val() < arrays[order[0]].val() )//if the third is less than the smallest of the others
        std::swap( order[0], order [1] );
}  
//else third pos of order is already correct

bool end = true;

for( i = 0; i < 3; ++i )
{   
    if( arrays[order[i]].MoveNext() )
    {
        end = false;
        break;
    }
}

if( end )//have gone through all the arrays

Answer 3

как насчет этого решения:

if (Ca != arraySize - 1) AND 
   ((Aa[Ca] == min(Aa[Ca], Ab[Cb], Ac[Cc]) OR 
    (Aa[Ca] == min(Aa[Ca], Ab[Cb]) And Cc == arraySize - 1) OR
    (Aa[Ca] == min(Aa[Ca], Ac[Cc]) And Cb == arraySize - 1) OR
    (Cc == arraySize - 1 And Cb == arraySize - 1))
{
    Ca++;
}
else if (Cb != arraySize - 1) AND 
        ((Ab[Cb] == min(Ab[Cb], Ac[Cc]) OR (Cc == arraySize - 1))
{
    Cb++;
}
else if (Cc != arraySize - 1) 
{
    Cc++;
}