加快重建阵列的效率

Question

如果我有两个整数数组，例如[100, 50, 32, 23] 和 [40, 30, 32, 125] 和一个数字 50 那么第一个数组中大于这个数字的数字应该连同它在第二个数组中的对应索引对一起被删除。

如果我对每个元素值都手动执行此操作，并在处理超过 10,000 个元素时每次都重建 int 数组，这不是令人难以置信 inefficient/slow 吗？

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

不确定我应该如何学习我应该去哪里或朝哪个方向寻找更 efficient/faster 的方法。

Answer 1

我会为你的 2 个数组创建一个 SortedMap，然后使用小于或等于你的输入参数的键提取对：

假设你的数组是这样的：

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].
此外，它假设键（第一个数组中的元素）是唯一的。

Answer 2

改进伪代码的一种方法是：

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.

Answer 3

这是一个 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]);

加快重建阵列的效率

Speed efficiency in rebuilding an array

arrays

sorting

pseudocode