найти значения второго массива на основе индекса первого массива

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. Индексы 6 в keys равны 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

Давайте игнорировать «элегантность» требование на данный момент, и иметь дело с реальной проблемой первой, которая является то, что вы

необходимости суммировать values[x], основываясь на изменяющемся keyValue, и не может включать повторение.

Чтобы предотвратить повторное использование значения, вы должны добавить массив used[], как показано ниже. Следующий алгоритм также позволяет изменение keyValue путем добавления while цикла:

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, тогда алгоритм может быть остановлен в этой точке.