Эффективность скорости при восстановлении массива - PullRequest
Новая
       6

Эффективность скорости при восстановлении массива

0 голосов
/ 11 октября 2019

Если у меня есть два массива целых чисел, например, [100, 50, 32, 23] и [40, 30, 32, 125] и число 50, то числа в первом массиве, который больше этого числа, должны быть удалены вместе с соответствующей парой индексов во втором массиве.

Если бы я делал это вручную для каждого значения элемента и перестраивал массив int каждый раз, когда проходил более 10000 элементов, разве это не было бы невероятно неэффективно / медленно? 

input 50:
new array changes:
[50, 32, 23]
[30, 32, 125]

псевдокод, такдалеко: for each value in array one that is greater than input, remove it and rebuild both arrays, continue

Не уверен, как я могу узнать, куда и в каком направлении мне следует идти, чтобы найти более эффективный / быстрый способ сделать это.

Ответы [ 3 ]

1 голос
/ 11 октября 2019

Вот реализация O (n) . Он проходит через массивы один раз, чтобы узнать, сколько элементов будет сохранено, создает новые массивы, которые тоже содержат результат, а затем копирует целые числа, которые должны быть меньше или равны пределу, в новые массивы. Я предполагаю, что эти два массива объединены в int[][], потому что это самый эффективный способ их передачи. 

public static int[][] removeGreaterThan(int[][] arrays, int limit) {
    int retained = 0;
    for (int i = 0; i < arrays[0].length; i++) {
        if (arrays[0][i] <= limit) retained++;
    }

    int[][] result = new int[][] {new int[retained], new int[retained]};
    int j = 0;
    for (int i = 0; i < arrays[0].length; i++) {
        if (arrays[0][i] <= limit) {
            result[0][j] = arrays[0][i];
            result[1][j] = arrays[1][i];
            j++;
        }
    }

    return result;
}

Используйте это так. 

int[][] arrays = new int[][] {{100, 50, 32, 23}, {40, 30, 32, 125}};
int[][] result = removeGreaterThan(arrays, 50);

// you can check to make sure the values are correct
System.out.println(Arrays.asList(result[0]);
System.out.println(Arrays.asList(result[1]);
1 голос
/ 11 октября 2019

Я бы создал SortedMap из ваших 2 массивов, а затем извлекал бы пары с ключом, меньшим или равным вашему входному параметру:

Предположим, что ваши массивы такие: 

int[] array_1;
int[] array_2;

Преобразуйте эти массивы в карту: 

NavigableMap<Integer, Integer> my_map = new TreeMap();
int                            index;
for (index = 0; index < array_1.length; index++)
  my_map.put(array_1[index], array_2[index]);

Теперь получите все пары со значением ключа, не превышающим указанное вами значение: 

NavigableMap<Integer, Integer> result;
result = my_map.headMap(50, true);

Преобразование результата в новые массивы:

array_1 = new int[result.size()];
array_2 = new int[array_1.length];
Iterator<Integer> it = result.keySet().iterator();
index = 0;
Integer key;
while (it.hasNext())
{
  key = it.next();
  array_1[index] = key;
  array_2[index] = result.get(key);
  index++;
}

Конечно, окончательный результат будет отсортирован. Не уверен, что это проблема.
Итак, ваш результат будет [23, 32, 50] [125, 32, 30].
Кроме того, он предполагает, что ключи (элементы в первом массиве) являются уникальными.

0 голосов
/ 11 октября 2019

Один из способов улучшить свой псевдокод: 

for each iteration
    find indexes of first array which are greater than the number.
    store indexes in a list.

remove all the elements of the first array using index list. // I can tell you more here but you should give it a try.
remove all the elements of the second array.
...