arrays - 根据第一个数组的索引查找第二个数组的值

Question

假设我有以下两个数组，带有 keyValue对象也是如此。

int[] values = {3, 1, 1, 2, 3};
int[] keys   = {6, 5, 5, 6, 9};
int   keyValue = 7;

我正在努力寻找最大的 value对于 key小于 keyValue .在上面的例子中，我们正在寻找 7。在这种情况下，正确答案是 3，因为最大的 key <= 7是6。keys中6的索引是0和3。所以我会看看value[0]和 value[3]并发现最大的是 value[0] = 3 .

如果我重新排序 keys我需要求助于这些值以确保索引匹配，所以我想保持两个列表相同。

我可以使用蛮力算法并做这样的事情

int foundValue = 0;
int foundKey = 0;
Foreach ( int x = 0; x < keys.length; x++ ){
    if ( keys[x] <= keyValue && keys[x] >= foundKey) {
      foundKey = keys[x];
      if(values[x] > foundValue){
         foundValue = values[x];
      }
   }
}

虽然有效，但并不是那么优雅。问题是我实际上需要对 values[x] 求和基于不断变化的 keyValue , 并且不能包括重复。例如

keyValue = 7    :    foundValue = 3
keyValue = 7    :    foundValue = 2   //because value[0] was already used
keyValue = 5    :    foundValue = 1   
keyValue = 10   :    foundValue = 3
keyValue = 7    :    foundValue = 1   //because all the 6 and one 5 value are used

有没有比蛮力更好的方法来解决这个问题？

Answer 1

我们暂时忽略“优雅”的要求，先处理真正的问题，那就是你

need to sum the values[x] based on a changing keyValue, and can't include repetition.

要防止重复使用某个值，您应该添加一个 used[] 数组，如下所示。以下算法还允许通过添加 while 循环来更改 keyValue:

int[] values = {3, 1, 1, 2, 3};
int[] keys   = {6, 5, 5, 6, 9};
bool[] used  = {false, false, false, false, false};
int   keyValue;

while (<We have a new keyvalue to try>) {
    keyValue = <new value>;
    int foundValue = 0;
    int foundKey = 0;
    Foreach ( int x = 0; x < keys.length; x++ ){
        if ( keys[x] <= keyValue &&
             keys[x] >= foundKey &&
             !used[x])
        {
            foundKey = keys[x];
            if(values[x] > foundValue) {
                foundValue = values[x];
                used[x] = true;
            }
        }
    }
}

为了使上面的代码更优雅，您可以执行以下操作:

• 将键和值配对在一起
• 按键降序排列键/值对
• 在搜索循环中，您可以在关键字匹配时立即跳到下一次迭代
• 您还可以检查 used[] 数组中的至少一个条目是否保持为 false，因为如果所有条目都为 true，然后算法可以在该点停止。