確定對應於一組數組中最小數據的索引

這是一個微不足道的算法問題，我相信，但我似乎無法找到一個高效優雅的解決方案。我們有3個int（Aa，Ab，Ac）數組和3個遊標（Ca，Cb，Cc），它們表示相應數組中的索引。我想識別並增加指向最小值的光標。如果這個遊標已經在數組的末尾，我會排除它並增加指向第二小值的光標。如果只有一個不在數組末尾的遊標，我們增加這個遊標。確定對應於一組數組中最小數據的索引

我能想出的唯一解決方案很複雜和/或不是最優的。舉例來說，我總是以一個巨大的if ... else結尾......

有沒有人看到這個問題的整潔解決方案？

我使用C++進行編程，但可以隨意用僞代碼或任何您喜歡的語言進行討論。

謝謝

來源

2011-03-11 Barth

如果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個元件的陣列。

來源

2011-03-11 11:48:22 MarcoS

這個怎麼解決辦法：

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

來源

2011-03-11 10:38:57

僞代碼：編輯：整理它一點

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

來源

2011-03-11 10:56:12 Patrick

確定對應於一組數組中最小數據的索引

回答

相關問題