识别一组数组中最小数据对应的索引

Question

我相信这是一个微不足道的算法问题，但我似乎无法找到有效而优雅的解决方案。

我们有 3 个 int 数组（Aa、Ab、Ac）和 3 个游标（Ca、Cb、Cc），它们指示相应数组中的索引。我想识别并增加指向最小值的光标。如果该游标已经位于数组的末尾，我将排除它并增加指向第二个最小值的游标。如果只有 1 个游标不在数组末尾，我们将增加该游标。

我能想到的唯一解决方案很复杂和/或不是最佳的。例如，我总是以一个巨大的 if...else... 结束，

有人看到这个问题的巧妙解决方案吗？

我正在使用 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. 用aa[ca]、ab[cb]初始化数组values和 ac[cc]

2. 对 值进行排序

3. 扫描值并在可能的情况下递增（即尚未位于数组的末尾）相应值的索引

，排序最多是 O(n lg n)，但我只对 3 个元素的数组进行排序。

Answer 2

这个解决方案怎么样：

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++;
}

Answer 3

伪代码：编辑：整理了一下

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