确定对应于一组数组中最小数据的索引

问题描述：

这是一个微不足道的算法问题，我相信，但我似乎无法找到一个高效优雅的解决方案。我们有3个int（Aa，Ab，Ac）数组和3个游标（Ca，Cb，Cc），它们表示相应数组中的索引。我想识别并增加指向最小值的光标。如果这个游标已经在数组的末尾，我会排除它并增加指向第二小值的光标。如果只有一个不在数组末尾的游标，我们增加这个游标。确定对应于一组数组中最小数据的索引

我能想出的唯一解决方案很复杂和/或不是最优的。举例来说，我总是以一个巨大的if ... else结尾......

有没有人看到这个问题的整洁解决方案？

我使用C++进行编程，但可以随意用伪代码或任何您喜欢的语言进行讨论。

谢谢

如果Aa [Ca] == Ab [Cb]> Ac [Cc]并且Ca和Cb都不指向它们各自阵列的末端会怎么样？你增加Ca或Cb吗？ – MarcoS 2011-03-11 10:20:31

这不是一个图形问题吗？ Dijkstra算法找到最短路径？ – Bytemain 2011-03-11 11:35:15

如果这里的意图是从三个数组中排序的数字流的输出从最低排序到最高排列，则可以简单地将所有三个数组放入一个更大的向量中，然后对其执行std :: sort – Patrick 2011-03-11 16:59:35

答

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

本质上，它确实如此以下：

初始化一个数组values与aa[ca]，ab[cb]和ac[cc]

排序values
扫描values和增量如果可能的话（即尚未在阵列的端部）对应的值

我知道的索引，排序是充其量为O（n LG n）的，但我只分拣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++; 
}

答

伪代码：编辑：整理它一点

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

确定对应于一组数组中最小数据的索引

相关推荐